Minimum insertions to make a string palindrome

1. The main idea is to use recursion to reduce the big problem into several small subproblems.
2. We will call a minimumInsertionsHelper function that returns us the minimum insertions required to make the string palindrome.
3. The idea is to compare the first character of the string str[i … j] with the last character. Now there are two possibilities.
   • If the first character of the string is the same as the last character, then we will do a recursive call for the remaining string str[i + 1 ... j - 1]. And our answer will be the answer of making the str[i + 1 … j - 1] palindrome.
   • If the first character of the string is different from the last character, then we will make 2 recursive calls, one for str[i + 1 ... j] and other for str[i … j - 1]. Let the answer from the calls is A and B, then our final answer will be min(A, B) + 1.
4. The algorithm for minimumInsertionsHelper function will be as follow:
   • int minimumInsertionsHelper(string 'str', int 'start', int 'end'):
     • If ('start' >= 'end') :
       • Return  0
     • If str[start] == str[end] :
       • Return minimumInsertionsHelper(str, start + 1, end - 1)
     • Else :
       • 'A' = minimumInsertionsHelper (STR, start + 1, end)
       • 'B' = minimumInsertionsHelper (STR, start, end - 1)
     • Return min(A, B) + 1

Let’s understand with an example:

Consider the string  'str' = “abcca” .

• Initially 'i' = 0 , 'j' = 4. Now, str[i] == str[j], the answer for “abcca” will be the answer for string “bcc”.
• Now 'i' = 1, 'j' = 3. Now str[i] != str[j]. Now we have 2 choices.
  • First, we add one ‘b’ after ‘c’ in “bcc” so it becomes “bccb” and then recursively find answer for str[2 … 3]. In this case, our answer will be 1 + answer for str[2 … 3].
  • Second, we add one ‘c’ before ‘b’ in “bcc” so it becomes “cbcc” and then recursively find answer for str[1 … 2]. In this case, our answer will be 1 + answer for str[1 … 2].
• As we want to minimize the number of insertions so the answer for str[1 … 3] = 1 + min( answer for STR[1..2] , answer for STR[2..3]).
• Now the answer for STR[1.2], i.e. “bc” is 1 and answer for str[2 ... 3], i.e. “cc” is 0. So, the answer for str[1..3] becomes 1 + min(1,0) = 1.
• So, the final answer is 1.

Let’s understand by an example:

Suppose we want to find the ans for string “abcde”, then the recursive tree for string “abcde” is :

As we can see in the above diagram:

• bc is calculated 3 times
• cd is calculated 3 times
• bcd is calculated 2 times

We can see that we were solving the same subproblems multiple times. Thus, this problem was exhibiting overlapping subproblems. 

This means, in this approach, we need to eliminate the need for solving the same subproblems again and again. Thus, the idea is to use Memoization.

This can be done as follows:

1. Create a 'lookUp' table of size 'n' * 'n' to store the answers to the subproblems where lookUp[i][j] denotes minimum insertion to make str[i..j] to a palindrome.
2. Initialize the 'lookUp' array with -1 which denotes that it is not calculated yet.
3. We will call a minimumInsertionsHelper function that returns us the minimum insertions.
4. The algorithm for minimumInsertionsHelper  function will be as follow:
   • int minimumInsertionsHelper(string 'str', int 'start', int 'end'):
     • If ('start' >= 'end'):
       • Return 0
     • If lookup[start][end] != -1,means we have already calculated the answer for this sub-problem,
       • Return lookup[start][end]
     • Let 'ans' = 0
     • If str[start] == str[end] :
       • 'ans' = minimumInsertionsHelper(str, start + 1, end - 1)
     • Else :
       • 'A' = minimumInsertionsHelper(str, start + 1, end)
       • 'B' = minimumInsertionsHelper(str, start, end - 1)
       • 'ans' = min(A, B) + 1
     • lookup[start][end] = ans, to store it for further use.
     • Return 'ans'

Initially, we were breaking the large problem into small problems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now. 

This can be done as follows:

1. Let 'n' = str.size
2. The idea is to create a 2-D 'dp' table of size 'n' * 'n'.
3. Each entry in 'dp' stores the solution to the subproblem i.e. dp[i][j] represents the minimum insertion needed to make str[i … j] palindrome.
4. Initialize 'dp' table entries with 0.
5. The algorithm for the 'dp' table will be as follows:
   • For 'len' from 1 to 'n' - 1:
     • For 'i' from 0 to (n - len):
       • Let 'j' = i + len - 1
       • If 'i' == 'j' :
         • dp[i][j] = 0
       • Else if str[i] == str[j] :
         • dp[i][j] = dp[i + 1][j - 1]
       • Else:
         • dp[i][j] = 1 + min(dp[i][j + 1] , dp[i - 1][j])
   • Returning the final answer dp[0][n - 1].

Let us understand with the example:

For the test case where 'str' = “abcca”.

• We will create a 'dp' table of size 'n' * 'n' i.e. 5 * 5, with all elements initialized to 0.
• Each entry in the table stores the solution to a subproblem i.e. dp[i][j] represents the minimum insertion needed to make the string str[i ... j] palindromic.
• The 'len' variable in the algorithm represents the length of the substring being considered in the current iteration.
• For the first iteration 'len' = 1, so consider all the substring with length 1. All the cells with i = j are filled in this iteration. Filling the table according to the conditions mentioned in the algorithm above, we get.

• For the second iteration 'len' = 2, so consider all the substring with length 2. All the cells with (i + 1) = j are filled in this iteration. Filling the table according to the conditions mentioned in the above algorithm, we get.

• For the third iteration 'len' = 3, so consider all the substrings with length 3. All the cells with (i + 2) = j are filled in this iteration. Filling the table according to the conditions mentioned in the above algorithm, we get.

• For the fourth iteration 'len' = 4, so consider all the substrings with length 4. All the cells with (i + 3) = j are filled in this iteration. Filling the table according to the conditions mentioned in the above algorithm, we get

• For the last iteration 'len' = 5, so consider all the substrings with length 5. All the cells with (i + 4) = j are filled in this iteration. Filling the table according to the conditions mentioned in the above algorithm, we get.

• Our final answer is dp[0][4].