Minimum Insertion Steps to Make a String Palindrome

This problem asks for the minimum number of insertions needed to make a given string a palindrome. We can solve this using dynamic programming.

Approach

The core idea is to build a DP table where dp[i][j] represents the minimum insertions needed to make the substring s[i...j] a palindrome.

Base Cases:

• dp[i][i] = 0 (a single character is already a palindrome)
• dp[i][i+1] = 0 or 1 (if s[i] == s[i+1], no insertion needed; otherwise, one insertion is needed)

Recursive Relation:

• If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] (because we can match the characters at i and j, reducing the problem to a smaller substring).
• If s[i] != s[j], then dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1. We have to insert a character, so we consider two options:
  • Insert a character to match s[i] with s[j], which is equivalent to dp[i+1][j] + 1
  • Insert a character to match s[j] with s[i], which is equivalent to dp[i][j-1] + 1 We choose the minimum of these two options.

Code Implementations

The solutions are presented using top-down (recursive with memoization) and bottom-up (iterative) dynamic programming approaches. Both achieve the same result.

Solution 1: Top-Down DP (Memoization)

This approach uses recursion with memoization to avoid redundant calculations.

class Solution:
    def minInsertions(self, s: str) -> int:
        @cache # this is python's lru_cache
        def dfs(i: int, j: int) -> int:
            if i >= j:
                return 0
            if s[i] == s[j]:
                return dfs(i + 1, j - 1)
            return 1 + min(dfs(i + 1, j), dfs(i, j - 1))
 
        return dfs(0, len(s) - 1)
 

Other languages (Java, C++, Go) use a similar recursive approach with a manually implemented memoization table (a 2D array). The logic remains the same.

Solution 2: Bottom-Up DP (Iterative)

This approach iteratively fills the DP table from smaller subproblems to larger ones.

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)] # dp table initialization
        for i in range(n - 2, -1, -1): # bottom up iteration
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1]
                else:
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
        return f[0][-1]

Again, other language implementations follow the same iterative approach with the appropriate DP table handling.

Solution 3: Optimized Bottom-Up DP

This version optimizes the bottom-up approach by iterating based on the length of the substring (k) rather than directly using nested loops for i and j.

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for k in range(2, n + 1):
            for i in range(n - k + 1):
                j = i + k - 1
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1]
                else:
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
        return f[0][n - 1]
 

Time and Space Complexity

Time Complexity: O(n^2) for all solutions, where n is the length of the string. This is due to the nested loops in the DP approaches.

Space Complexity: O(n^2) for all solutions, to store the DP table. The recursive solution might use less space in practice due to the memoization, but the worst-case space complexity is still O(n^2) due to the recursion depth. The bottom-up approaches have a constant space complexity if you optimize the memory usage by using only one row for the DP table. However, I showed the solution that utilizes the full DP table for easier understanding.