This question was asked in hacker rank to fix the minor bug in the program such a way it passes all the tests.
Problem is evident from the title.
Sample input and output.
Input: aba
Output: 0
Input: bptp
Output: 1
Input: a
Output: 0
Input: abc
Output: 2
Will discuss recursive approach here. As they provided most of the code and asked interviewee to fix the bug.
Just a basic understanding of code flow. It a recursive solution. At each stage think about possible cases.
Check: characters at start index and end index are same
If yes : means you do not need to insert at this stage, increment start index and decrement end index
If not: there can be two parallel case
- Assume we inserted first character at the end, so we left with string startIndex+1 to endindex.
Example: trump > rump . Here, we assumed we inserted t at the end trumpt.
- Vise versa.
Example: trump > trum. Here, we assumed we inserted p at the start ptrump.
In both of above case we increment 1 the total count.
So, for each recursive call, propagate the minimum value to the caller and that will be your answer.
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class FindMinInsertions { static int min(int a, int b) { return a < b ? a : b; } static int findMinInsertions(String a, int start, int totalLength) { char[] str = a.toCharArray(); if (start > totalLength) return Integer.MAX_VALUE; if (start == totalLength) return 0; if (start == totalLength - 1) return (str[start] == str[totalLength]) ? 0 : 1; return (str[start] == str[totalLength]) ? findMinInsertions(new String(str), start + 1, totalLength - 1) : (min(findMinInsertions(new String(str), start, totalLength - 1), findMinInsertions(new String(str), start + 1, totalLength)) + 1); } public static void main(String[] args) { String inputString = "abc"; System.out.println(findMinInsertions(inputString, 0, inputString.length() - 1)); } } |
Complexity: O(n * n)
Git url : https://github.com/Niravkumar-Patel/SnippetExampleRepo/blob/master/SnippetExamplePractice/src/interviewque/FindMinInsertions.java