Minimum Insertions to Make a String Palindrome
January 6, 2024
Problem #
Given a string containing only digits, find the minimum number of characters to be inserted to make it a palindrome.
Solution #
To solve this problem, we need to find the longest palindromic subsequence in the given string. The minimum number of characters to be inserted to make the string a palindrome is equal to the length of the string minus the length of the longest palindromic subsequence.

Dynamic Programming (DP) to Find Longest Palindromic Subsequence:
 We will use a DP table to store the lengths of the longest palindromic subsequences of substrings of the input string.
 The table
dp[i][j]
will represent the length of the longest palindromic subsequence in the substring from indexi
toj
.

Fill DP Table:
 Initialize a 2D array
dp
with dimensionsn x n
, wheren
is the length of the string.  Fill the diagonal of the DP table with 1, as every single character is a palindrome of length 1.
 For substrings of length 2 to
n
, check if the characters at the end of the substring are equal. If they are, add 2 to the length of the longest palindromic subsequence of the substring excluding these two characters; otherwise, take the maximum length found in the substrings obtained by removing either the first or the last character.
 Initialize a 2D array

Calculate Minimum Insertions:
 The length of the longest palindromic subsequence can be found in
dp[0][n1]
.  The minimum number of insertions required is
n  dp[0][n1]
.
 The length of the longest palindromic subsequence can be found in
Python Code #
def minInsertionsToMakePalindrome(s):
n = len(s)
dp = [[0 for _ in range(n)] for _ in range(n)]
# Every single character is a palindrome of length 1
for i in range(n):
dp[i][i] = 1
# Fill up the DP table
for length in range(2, n + 1):
for i in range(n  length + 1):
j = i + length  1
if s[i] == s[j]:
dp[i][j] = 2 + dp[i + 1][j  1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j  1])
# Minimum insertions to make the string palindrome
return n  dp[0][n  1]
# Example Usage
string = "12321"
print(minInsertionsToMakePalindrome(string))
Time Complexity #
 O(n^2): We iterate through each substring and fill the DP table, where
n
is the length of the string.
Space Complexity #
 O(n^2): The space complexity is dominated by the 2D DP table.
This dynamic programming approach efficiently solves the problem by reusing previously computed values, a common strategy in solving optimization problems like this one.