Minimum insertions to make a string palindrome

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
146 upvotes
Asked in companies
FacebookAppleSamsung

Problem statement

A palindrome string is one that reads the same backward as well as forward.


You are given a string 'str'.


Find the minimum number of characters needed to insert in 'str' to make it a palindromic string.


Example : 
Input: 'str' = "abca"

Output: 1

Explanation:
If we insert the character ‘b’ after ‘c’, we get the string "abcba", which is a palindromic string. Please note that there are also other ways possible.


Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains a string 'str', containing lowercase English letters i.e from ‘a’ to ‘z’.


Output format: 
The output contains a single integer denoting the minimum number of insertions needed to make 'str' palindrome.


Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1:
abca


Sample Output 1:
1


Explanation for input 1:
If we insert the character ‘b’ after ‘c’, we get the string "abcba", which is a palindromic string. Please note that there are also other ways possible.


Sample Input 2:
abcdefg


Sample Output 2:
6


Sample Input 3:
aaaaa


Sample Output 3:
0


Expected time complexity :
The expected time complexity is O(|str| ^ 2).


Constraints:
1 <= |str| <= 1000

Where |str| represents the length of the string 'str'.

Time Limit: 1 sec.
Hint

The very first approach can be to try all possible substrings of the string and minimize the ans among the valid ones.

Approaches (3)
Brute Force
  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.
Time Complexity

O(2 ^ n), where 'n' is the length of the string. 

In the worst case, at every step, we are making 2 recursive calls. Hence, the overall complexity is O(2 ^ n).

Space Complexity

O(n), where 'n' is the length of the string. 

In the worst case, extra space is used by the recursion stack which goes to a maximum depth of 'n'.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Minimum insertions to make a string palindrome
Full screen
Console