Minimum Insertions to Make a String Palindrome

Minimum Insertions to Make a String Palindrome

January 6, 2024
medium
dynamic programming

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.

  1. 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 index i to j.

  2. Fill DP Table:

    • Initialize a 2D array dp with dimensions n x n, where n 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.

  3. Calculate Minimum Insertions:

    • The length of the longest palindromic subsequence can be found in dp[0][n-1].
    • The minimum number of insertions required is n - dp[0][n-1].

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.