Minimum Insertion Steps to Make a String Palindrome

hard dp strings

Problem

Given a string s, in one step you can insert any character at any position. Return the minimum number of steps to make s a palindrome.

Inputs = "leetcode"

Output5

Longest palindromic subsequence = LCS(s, reverse(s)) = 3 ("e..e..e"). Insertions = 8 − 3 = 5.

s (string)

def min_insertions(s):
    n = len(s)
    t = s[::-1]
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return n - dp[n][n]

function minInsertions(s) {
  const n = s.length;
  const t = s.split("").reverse().join("");
  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] === t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return n - dp[n][n];
}

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        String t = new StringBuilder(s).reverse().toString();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return n - dp[n][n];
    }
}

int minInsertions(string s) {
    int n = s.size();
    string t(s.rbegin(), s.rend());
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return n - dp[n][n];
}

Explanation

The neat realization is that the characters you don't need to touch are exactly the longest palindromic subsequence of s. Everything else has to be mirrored with an insertion, so the answer is n - (length of that palindrome).

And the longest palindromic subsequence of s equals the longest common subsequence (LCS) of s and its reverse t. So the whole problem reduces to a standard LCS table.

We fill dp[i][j] = LCS length of the first i chars of s and first j chars of t. When s[i-1] == t[j-1] we extend a match: dp[i-1][j-1] + 1. Otherwise we drop one character and take the better of dp[i-1][j] or dp[i][j-1]. The result is n - dp[n][n].

Example: s = "leetcode" (n=8). Its longest palindromic subsequence has length 3 (an e..e..e pattern), so we need 8 - 3 = 5 insertions.

Building the n × n table with constant work per cell makes this O(n²).

Time: O(n²) Space: O(n²)