Proficient Level
Implement the minimumInsertionsToPalindrome method that finds the minimum insertions required to make the text a palindrome.
The input contains a string text. Your task is to return the minimum number of characters that must be inserted to make the string a palindrome.
You may insert characters at any position. For example, abcda can be converted into a palindrome with 2 insertions.
Example 1
Input
text (string) =
abcdaReturns (int)
2Example 2
Input
text (string) =
raceReturns (int)
3Example 3
Input
text (string) =
madamReturns (int)
0The minimum insertions can be found using the longest palindromic subsequence.
Characters already included in the longest palindromic subsequence can stay as they are. The remaining characters need matching characters to be inserted.
So the answer is length of string - length of longest palindromic subsequence.
Pseudocode:
function minimumInsertionsToPalindrome(text):
n = length(text)
lps = longestPalindromicSubsequenceLength(text)
return n - lps
function longestPalindromicSubsequenceLength(text):
n = length(text)
dp = 2D array of size n x n filled with 0
for i from 0 to n - 1:
dp[i][i] = 1
for lengthValue from 2 to n:
for left from 0 to n - lengthValue:
right = left + lengthValue - 1
if text[left] == text[right]:
dp[left][right] = 2 + dp[left + 1][right - 1]
else:
dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
return dp[0][n - 1]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run