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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Insertion Steps to Make a String Palindrome

Number: 1437

Difficulty: Hard

Paid? No

Companies: Meta, Amazon, Adobe, Squarepoint Capital

Problem Description

Given a string s, you can insert any character at any index. The goal is to determine the minimum number of insertions required to make s a palindrome. A palindrome is a string that reads the same forwards and backwards.

Key Insights

  • The problem can be re-framed in terms of finding the Longest Palindromic Subsequence (LPS) in the given string.
  • The minimum number of insertions required is equal to the length of the string minus the length of the LPS.
  • Dynamic Programming (DP) is used to compute the LPS efficiently by solving overlapping subproblems.
  • A bottom-up DP approach iterating over smaller substrings and expanding them is effective.

Space and Time Complexity

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

Solution

We use dynamic programming to compute the longest palindromic subsequence (LPS) of the given string. We initialize a 2D dp array where dp[i][j] stores the length of the LPS in the substring s[i...j].

  • If s[i] equals s[j], then dp[i][j] is 2 plus dp[i+1][j-1] (or 1 if i equals j).
  • If they do not match, dp[i][j] takes the maximum value from dp[i+1][j] or dp[i][j-1]. After filling the dp table for the entire string, the minimum insertions required is the difference between the string's length and the LPS length (i.e., len(s) - dp[0][n-1]).
    This approach efficiently fills out the DP table in a bottom-up manner.

Code Solutions

# Python solution using Dynamic Programming
def minInsertions(s: str) -> int:
    n = len(s)
    # Create a 2D DP array where dp[i][j] denotes the length of LPS in s[i...j]
    dp = [[0] * n for _ in range(n)]
    
    # Every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1
    
    # Check substrings of increasing lengths
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                # When matching and if length == 2, then it forms a palindrome of length 2
                dp[i][j] = 2 + (dp[i + 1][j - 1] if length > 2 else 0)
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    lps = dp[0][n - 1]
    return n - lps

# Example usage:
print(minInsertions("mbadm"))  # Expected output: 2
← Back to All Questions