Minimum Insertions

Moderate
0/80
Average time to solve is 20m
10 upvotes
Asked in companies
ShareChatAmazonDunzo

Problem statement

You are given a string 'STR' of length 'N' consisting of lowercase English Alphabet letters. Your task is to return the count of minimum characters to be added to make the string a palindrome.

You can add any number of characters at any positions in the string like in the beginning, or between two characters of the string or at the end of the string.

For example:

For the given string “deed”, the string is already a palindrome, thus, minimum characters needed to be added are 0. 

Similarly, for the given string “abb”, the minimum characters needed is 1 i.e. ‘a’ which is to be added to the end of the string,  which makes the string “abba”, which is a palindrome.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case contains the string 'STR'.
Output format: 
For each test case, print the count of minimum characters needed to make the string palindrome.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10 ^ 2 
1 <= N <= 10 ^ 4
'STR' contains only lowercase English letters.

Time limit: 1 second
Sample input 1:
2
abcd
dad
Sample output 1:
3
0
Explanation For Sample Input 1:
In the first test case, the minimum characters to be added at front to make it a palindrome are 3 i.e. “dcb” which makes the string “dcbabcd”.

In the second test case, the string is already a palindrome, we do not need to add any character.
Sample input 2:
2
xxaxxa    
abb
Sample output 2:
1
1
Explanation For Sample Input 2:
In the first test case, the minimum number of characters to be added at front to make it a palindrome is 1 i.e. “a” which makes the string “axxaxxa”.

In the second test case, the minimum number of characters to be added at end to make it a palindrome is 1 i.e. “a” which makes the string “abba”.
Hint

Can we solve this problem with the help of recursion?

Approaches (3)
Using Recursion

For an interval [ ‘l’, ‘r’ ], in order to make it a palindrome using minimum insertions we have to consider the following cases-

 

  • If( ‘STR[l]’ == ‘STR[r]’), then the answer will be equal to the answer for the interval [ ‘l’ + 1, ‘r’ - 1].
  • Else, the answer will be equal to the min(answer for the interval [ ‘l’ + 1, ‘r’ ] , answer for the interval [ ‘l’, ‘r’ - 1]) + 1.

We can write a recursive solution based on these observations.

 

The algorithm will be:

  1. We call a recursion ‘minInsertion’ keeping the interval [ ‘l’, ‘r’ ] for which we want to find our answer as the parameter. We initially call the recursion as minInsertions(0, len of STR - 1).
  2. In each recursive call, we will-
    • If (‘l’ == ‘r’), we return 0 as a string of length 1 is also a palindrome.
    • If (‘l’ == ‘r’ - 1):
      • If ( ‘STR[l]’ == ‘STR[r]’) we return 0.
      • Else, we return 1.
    • If ( ‘STR[l]’ == ‘STR[r]’):
      • Return minInsertions(l + 1, r - 1).
    • Else return 1 + min(minInsertions(l +1, r), minInsertions(l, r - 1)).
Time Complexity

O(2 ^ N), where N is the length of ‘STR’.

 

The size of the recursion tree for each recursive call can be O(2 ^ N). So, the overall time complexity will be O(2 ^ N).

Space Complexity

O(N), where N is the length of ‘STR’.

 

As there will be 2 ^ N states of recursion in total the size of the recursion stack can go up to O(N). Hence, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimum Insertions
Full screen
Console