We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Insertion Steps to Make a String Palindrome

Difficulty: Hard

Problem Description

Given a string s. In one step you can insert any character at any index of the string. Return the minimum number of steps to make s palindrome. A Palindrome String is one that reads the same backward as well as forward.

Key Insights

  • To make a string palindrome, we can insert characters to match corresponding characters from both ends.
  • The problem can be solved using dynamic programming by finding the longest palindromic subsequence.
  • The minimum insertions required will be equal to the length of the string minus the length of the longest palindromic subsequence.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

The approach to solve this problem involves using dynamic programming to calculate the length of the longest palindromic subsequence (LPS) in the string. The idea is to fill a 2D table where each entry dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j].

  1. If the characters at the ends of the current substring are the same (s[i] == s[j]), then they are part of the LPS and we increment the count from the inner substring s[i+1...j-1].
  2. If they are not the same, we take the maximum length by either ignoring the left character or the right character.
  3. The base case is that single-character substrings are palindromes of length 1.

After filling the table, the minimum insertions required will be the total length of the string minus the length of the LPS.

Code Solutions

def min_insertions(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = 1  # Single character palindromes
    
    for length in range(2, n + 1):  # Length of substring
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    lps = dp[0][n - 1]
    return n - lps
← Back to All Questions