Minimum Insertion Steps to Make a String Palindrome | Leetcode 1312

Given a string s, return the minimum number of insertions needed to make s a palindrome. You can insert characters at any positions.

Key observation: the minimum insertions required equals
len(s) - LPS(s)
where LPS(s) is the length of the Longest Palindromic Subsequence in s. Since LPS(s) = LCS(s, reverse(s)), this problem reduces to computing the Longest Common Subsequence between s and reverse(s).

Here’s the [Problem Link] to begin with.

Example 1

Input:  s = "zzazz"
Output: 0
Explanation: Already a palindrome.

Example 2

Input:  s = "mbadm"
Output: 2
Explanation: One optimal result is "mbdadbm" after 2 insertions.

Intuition and Approach

1. Let s1 = s and s2 = reverse(s).
2. Compute lcs = LCS(s1, s2).
3. Answer is len(s) - lcs, because characters already part of a palindromic subsequence do not need insertion. Only the remaining characters must be matched by insertions.

Below are three implementations that follow this plan.

Memoization

Intuition and Approach

Use top down recursion with caching on indices (ind1, ind2) over s1 and s2. If characters match, move diagonally and add 1. Otherwise, take the maximum of skipping one character from either string. The LCS value then gives the minimum insertions as n - lcs.

Code Implementation

class Solution:
    def solve(self, text1: str, text2: str, ind1: int, ind2: int, dp) -> int:
        if ind1 == 0 or ind2 == 0:
            return 0
        if dp[ind1][ind2] != -1:
            return dp[ind1][ind2]
        if text1[ind1 - 1] == text2[ind2 - 1]:
            dp[ind1][ind2] = 1 + self.solve(text1, text2, ind1 - 1, ind2 - 1, dp)
        else:
            dp[ind1][ind2] = 0 + max(
                self.solve(text1, text2, ind1 - 1, ind2, dp),
                self.solve(text1, text2, ind1, ind2 - 1, dp),
            )
        return dp[ind1][ind2]

    def minInsertions(self, s: str) -> int:
        s1 = s
        s2 = s[::-1]
        n = len(s1)
        m = len(s2)
        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
        lcs = self.solve(s1, s2, n, m, dp)
        return len(s) - lcs

Code explanation

• solve(ind1, ind2) returns the LCS length for prefixes s1[:ind1] and s2[:ind2].
• Base case when either prefix is empty returns 0.
• On character match, move diagonally and add 1.
• On mismatch, choose the better of skipping from s1 or s2.
• minInsertions computes lcs and returns len(s) - lcs.

Time and Space Complexity

• Precise: O(n*m) states with O(1) work per state after memoization, so O(n*m) time. DP table space O(n*m), recursion depth up to O(n + m).
• Simplified: O(n*m) time and O(n*m) space.

Conclusion

Memoization captures overlapping subproblems and is efficient for typical constraints while keeping code close to the recurrence.

Tabulation

Intuition and Approach

Bottom up LCS table for s1 and s2 = reverse(s). Initialize row 0 and column 0 to 0. Fill the table using standard LCS transitions. Result is len(s) - dp[n][m].

Code Implementation

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
        for ind2 in range(0, m + 1):
            dp[0][ind2] = 0
        for ind1 in range(0, n + 1):
            dp[ind1][0] = 0
        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                if text1[ind1 - 1] == text2[ind2 - 1]:
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
                else:
                    dp[ind1][ind2] = 0 + max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
        return dp[n][m]

    def minInsertions(self, s: str) -> int:
        s1 = s
        s2 = s[::-1]
        return len(s) - self.longestCommonSubsequence(s1, s2)

Code explanation

• Builds a (n+1) x (m+1) LCS table with base zeros for empty prefixes.
• Fills each cell from previous row and column values according to match or mismatch.
• Uses dp[n][m] as the LCS length to compute the answer.

Time and Space Complexity

• Precise: O(n*m) time to fill the table, O(n*m) space to store it.
• Simplified: O(n*m) time and space.

Conclusion

Iterative and stable. Useful when you might also want to reconstruct a palindromic subsequence.

Tabulation (Space Optimize)

Intuition and Approach

The LCS transition for dp[i][j] uses only dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. Maintain only two rows to reduce space to linear in the second string.

Code Implementation

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        prev = [0] * (m + 1)

        for ind1 in range(1, n + 1):
            cur = [0] * (m + 1)
            for ind2 in range(1, m + 1):
                if text1[ind1 - 1] == text2[ind2 - 1]:
                    cur[ind2] = 1 + prev[ind2 - 1]
                else:
                    cur[ind2] = 0 + max(prev[ind2], cur[ind2 - 1])
            prev = cur

        return prev[m]

    def minInsertions(self, s: str) -> int:
        s1 = s
        s2 = s[::-1]
        return len(s) - self.longestCommonSubsequence(s1, s2)

Code explanation

• prev holds results for the previous row, cur for the current row.
• Update cur[j] from prev[j-1], prev[j], and cur[j-1].
• After processing a row, set prev = cur.
• Final LCS is prev[m], so answer is len(s) - prev[m].

Time and Space Complexity

• Precise: O(n*m) time. Arrays of size m+1 give O(m) extra space.
• Simplified: O(n*m) time and O(min(n, m)) space if you iterate columns over the shorter string.

Conclusion

Same optimal time with significantly less memory, ideal when only the count of insertions is required.

Final takeaway

• Minimum insertions to make s a palindrome equals len(s) - LCS(s, reverse(s)).
• Memoization, tabulation, and space optimized tabulation all run in O(n*m) time, with space ranging from O(n*m) down to O(min(n, m)).
• Use the full table if you need to reconstruct a palindromic subsequence; use the space optimized version when memory is a priority and only the count is needed.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.