String Dynamic Programming Tabulation
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) = abcda
Return:
(int) 2
Example 2
Input:
text (string) = race
Return:
(int) 3
Example 3
Input:
text (string) = madam
Return:
(int) 0

The 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]
Run your code to see the result.