Minimum Insertion Steps to Make a String Palindrome

HARD

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.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

Approaches

Checkout 4 different approaches to solve Minimum Insertion Steps to Make a String Palindrome. Click on different approaches to view the approach and algorithm in detail.

Tabulation (Bottom-Up DP)

This approach uses an iterative, bottom-up method to solve the problem. It builds the solution from smaller subproblems to larger ones using a 2D DP table, avoiding recursion entirely. The recurrence relation is the same as in the previous approaches.

Algorithm

Create a 2D DP table, dp[n][n], where dp[i][j] will store the minimum insertions for s[i...j].
The base cases, dp[i][i] = 0, are implicitly handled by initializing the array with zeros.
Iterate through substring lengths len from 2 to n.
For each len, iterate through all possible start indices i from 0 to n-len.
Calculate the end index j = i + len - 1.
Apply the transition formula:
- If s[i] == s[j], then dp[i][j] = dp[i+1][j-1].
- If s[i] != s[j], then dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]).
The final answer is dp[0][n-1].

Instead of a top-down recursive approach, we can solve the problem iteratively in a bottom-up fashion. We use a 2D array dp[n][n], where dp[i][j] stores the minimum insertions to make s[i...j] a palindrome. We fill this table for substrings of increasing length. Substrings of length 1 are already palindromes, so dp[i][i] = 0. We then compute the values for substrings of length 2, then 3, and so on, up to n. When calculating dp[i][j], the values for the smaller subproblems it depends on (dp[i+1][j-1], dp[i+1][j], dp[i][j-1]) will have already been computed. The final result for the entire string s[0...n-1] is stored in dp[0][n-1].

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n^2). The nested loops iterate through all `O(n^2)` subproblems, and each calculation is constant time.Space Complexity: O(n^2) for the 2D DP table.

Pros and Cons

Pros:

Avoids recursion overhead, which can make it slightly faster in practice than memoization.
Can be more intuitive for those who prefer iterative solutions.

Cons:

Requires O(n^2) space, same as the memoization approach.

Code Solutions

Checking out 3 solutions in different languages for Minimum Insertion Steps to Make a String Palindrome. Click on different languages to view the code.

class Solution {
private
  Integer[][] f;
private
  String s;
public
  int minInsertions(String s) {
    this.s = s;
    int n = s.length();
    f = new Integer[n][n];
    return dfs(0, n - 1);
  }
private
  int dfs(int i, int j) {
    if (i >= j) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = 1 << 30;
    if (s.charAt(i) == s.charAt(j)) {
      ans = dfs(i + 1, j - 1);
    } else {
      ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
    }
    return f[i][j] = ans;
  }
}

Video Solution

Watch the video walkthrough for Minimum Insertion Steps to Make a String Palindrome

Patterns:

Dynamic Programming

Data Structures:

String

Companies:

Arcesium |