Find Minimum Insertions to form a palindrome string ( Hacker rank interview question)

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.

Recursive call tree

Complexity: O(n * n)

Git url :

Leave a Reply

Your email address will not be published. Required fields are marked *