Last Updated: 3 Jan, 2021
Minimum Insertions
Moderate
Asked in companies
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.
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
Approaches
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:
- 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).
- 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)).
We can use memoization to optimize the recursive approach. Since many recursive calls have to be made with the same parameters, this redundancy can be eliminated by storing the results obtained for a particular call in memoization in a matrix ‘MEMO’.
We can also solve this problem with the help of dynamic programming similar to previous approaches.
The algorithm will be:
- We will create a matrix ‘DP’ of size ‘N’ * ‘N’, with each ‘DP[i][j]’ storing the answer for the substrings of ‘STR’ from ‘i’ to ‘j’.
- We will iterate over all substrings of ‘STR’ in the increasing order of their length.
- For each substring of ‘STR’ from ‘i’ to ‘j’:
- If( ‘STR[i]’ == ‘STR[j]’ ), we set ‘DP[i][j]’ to ‘DP[i + 1][j - 1]’.
- Else, we set ‘DP[i][j]’ to min(‘DP[i + 1][j]’, ‘DP[i][j - 1]’) + 1.
- We finally return ‘DP[0][N - 1]’ as our answer.
Similar problems