☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Minimum insertions to make string palindrome - DP-29

Hard TUF ID 2800 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, you may insert any character at any position, as many times as you like. Return the minimum number of insertions needed to make s a palindrome.

Constraints (LeetCode 1312): 1 ≤ n ≤ 500, lowercase English letters. The Java methods also accept the empty string.

Example 1

s = "mbadm"
answer = 2          // "mbdadbm" or "mdbabdm"

Example 2

s = "leetcode"
answer = 5          // e.g. "leetcodocteel"

Key insight: keep a palindrome, mirror the rest

Every original character ends up somewhere in the final palindrome, and its mirror position holds either another original character or an inserted one.

So answer = n - LPS(s). The same reasoning on a range s[i..j] gives a direct recurrence for f(i, j), the fewest insertions for that range:

Each line is exactly “range length minus LPS of the range” rewritten, so the two views always agree.

Approach 1: Recursion

Intuition. Try both ways of fixing a mismatched end and keep the cheaper; matching ends cost nothing.

Algorithm.

  1. If i >= j, return 0.
  2. If s[i] == s[j], return f(i + 1, j - 1).
  3. Otherwise return 1 + min(f(i + 1, j), f(i, j - 1)).
static int recursive(String s) {
    return solve(0, s.length() - 1, s);
}

/** Fewest insertions that turn s[i..j] (inclusive) into a palindrome. */
static int solve(int i, int j, String s) {
    if (i >= j) return 0;                                    // empty or one character: already a palindrome
    if (s.charAt(i) == s.charAt(j)) return solve(i + 1, j - 1, s);   // the ends already pair up
    return 1 + Math.min(solve(i + 1, j, s),                  // insert a copy of s[i] after j
                        solve(i, j - 1, s));                 // insert a copy of s[j] before i
}

Complexity. Time O(2^n): with all-distinct letters each call branches twice and each branch shrinks the range by one. Space O(n) for the stack.

Approach 2: Memoization

Intuition. Only O(n^2) ranges exist, and both branches of a mismatch reach (i + 1, j - 1) again one level down. Cache every range’s answer; -1 means “not computed” because the true answer is never negative.

Algorithm.

  1. dp[n][n] filled with -1.
  2. Same recursion, returning stored answers and storing new ones.
static int memoization(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, n - 1, s, dp);
}

static int memo(int i, int j, String s, int[][] dp) {
    if (i >= j) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    if (s.charAt(i) == s.charAt(j)) return dp[i][j] = memo(i + 1, j - 1, s, dp);
    return dp[i][j] = 1 + Math.min(memo(i + 1, j, s, dp), memo(i, j - 1, s, dp));
}

Complexity. Time O(n^2), space O(n^2) plus O(n) stack.

Approach 3: Tabulation

Intuition. A range reads the range starting one later (row i + 1) and the range ending one earlier (same row, column j - 1). So i runs from n - 1 down to 0 and j runs upward from i + 1. The diagonal and everything below it are 0, which covers both base cases, including dp[i + 1][j - 1] when j == i + 1.

Algorithm.

  1. For i = n - 1 .. 0, j = i + 1 .. n - 1: apply the recurrence.
  2. Return dp[0][n - 1].
static int tabulation(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[][] dp = new int[n][n];                              // dp[i][i] = 0 and i > j entries stay 0
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            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];
}

Dry run on s = "mbadm":

i \ j 0 m 1 b 2 a 3 d 4 m
0 m 0 1 2 3 2
1 b   0 1 2 3
2 a     0 1 2
3 d       0 1
4 m         0

Every pair of different adjacent letters costs 1. dp[1][3] (“bad”) is 1 + min(dp[2][3], dp[1][2]) = 2. The corner dp[0][4] has matching ends m, so it copies dp[1][3] = 2.

Complexity. Time O(n^2), space O(n^2).

Approach 4: Space optimized

Intuition. Row i needs only row i + 1 (next) and the part of row i already filled (cur). Two arrays suffice. When j == i + 1 the inner range is empty and the code uses 0 directly instead of reading next[i], so correctness does not depend on what the recycled array happens to contain.

Algorithm.

  1. For i = n - 1 .. 0: cur[i] = 0; fill cur[j] for j > i; swap cur and next.
  2. Return next[n - 1].
static int spaceOptimized(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[] next = new int[n], cur = new int[n];               // next = row i + 1, cur = row i
    for (int i = n - 1; i >= 0; i--) {
        cur[i] = 0;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) cur[j] = j - 1 > i ? next[j - 1] : 0;  // j == i + 1: nothing inside
            else cur[j] = 1 + Math.min(next[j], cur[j - 1]);
        }
        int[] tmp = next; next = cur; cur = tmp;
    }
    return next[n - 1];
}

Complexity. Time O(n^2), space O(n).

Approach 5: Via the longest palindromic subsequence

Intuition. Use the identity from the key insight directly. The LPS of s equals the longest common subsequence of s and its reverse, which two LCS rows compute. Subtract it from n.

static int viaLps(String s) {
    String r = new StringBuilder(s).reverse().toString();
    int n = s.length();
    int[] prev = new int[n + 1], cur = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == r.charAt(j - 1)) cur[j] = 1 + prev[j - 1];
            else cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return n - prev[n];                                      // prev[n] = LCS(s, reverse(s)) = LPS(s)
}

Complexity. Time O(n^2), space O(n). This is the route the A2Z sheet takes: it turns a new problem into one already solved, at the cost of filling a full n × n table instead of half of one.

Edge cases and pitfalls