Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Insertion Steps to Make a String Palindrome

HARDProblemSolveExternal Links

Description

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

A palindrome is a string that reads the same forwards and backwards. For example, "racecar" and "abba" are palindromes, while "hello" is not.

You are allowed to insert characters at the beginning, end, or anywhere in the middle of the string. Each insertion counts as one step, and you want to minimize the total number of insertions.

Examples

Example 1

Input: s = "zzazz"

Output: 0

Explanation: The string "zzazz" is already a palindrome — it reads the same forwards (zzazz) and backwards (zzazz). No insertions are needed.

Example 2

Input: s = "mbadm"

Output: 2

Explanation: We can make it a palindrome in 2 insertion steps. For instance, insert 'b' after the second 'm' and insert 'd' before the first 'm' to get "mdbabdm", which is a valid palindrome. Another valid result is "mbdadbm". Both require exactly 2 insertions.

Example 3

Input: s = "leetcode"

Output: 5

Explanation: By inserting 5 characters, the string can become "leetcodocteel", which is a palindrome. This is the minimum number of insertions possible.

Constraints

  • 1 ≤ s.length ≤ 500
  • s consists of lowercase English letters only.

Editorial

Brute Force

Intuition

To think about this problem from scratch, imagine holding the string with one hand at the beginning and one hand at the end. You compare the first and last characters:

  • If they match, they are already mirrored. You can move both hands inward and focus on the remaining inner substring — no insertion needed for this pair.
  • If they don't match, you need to fix this mismatch by inserting a character. You have two options: insert a copy of the last character at the front (so now the front matches, and you shrink the problem from the right side), or insert a copy of the first character at the end (so the end matches, and you shrink from the left side). You pick whichever option leads to fewer total insertions.

This naturally leads to a recursive solution. For any substring s[l..h]:

  • Base case: If l >= h, the substring is empty or a single character — already a palindrome, requiring 0 insertions.
  • Match case: If s[l] == s[h], the answer is solve(l+1, h-1) — just recurse on the inner part.
  • Mismatch case: If s[l] != s[h], the answer is 1 + min(solve(l+1, h), solve(l, h-1)) — we pay 1 insertion and take the better of the two shrinking options.

Step-by-Step Explanation

Let's trace through with s = "mbadm":

Step 1: Call solve(0, 4). Compare s[0]='m' with s[4]='m'. They match! The outer characters already mirror each other, so no insertion is needed. Recurse on the inner substring: solve(1, 3).

Step 2: Call solve(1, 3). Compare s[1]='b' with s[3]='d'. They don't match. We branch into two recursive calls: solve(2, 3) (skip left) and solve(1, 2) (skip right). The answer will be 1 + min(solve(2,3), solve(1,2)).

Step 3: Call solve(2, 3). Compare s[2]='a' with s[3]='d'. No match. Branch into solve(3, 3) and solve(2, 2).

Step 4: Base case: solve(3, 3) → single character 'd', already a palindrome. Return 0.

Step 5: Base case: solve(2, 2) → single character 'a', return 0.

Step 6: Resolve solve(2, 3) = 1 + min(0, 0) = 1. We need one insertion to make "ad" a palindrome (e.g., insert 'a' to get "ada").

Step 7: Call solve(1, 2). Compare s[1]='b' with s[2]='a'. No match. Branch into solve(2, 2) and solve(1, 1).

Step 8: solve(2, 2) = 0. Notice this was already computed in Step 5 — this is an overlapping subproblem! The recursion recomputes it from scratch.

Step 9: Base case: solve(1, 1) = 0.

Step 10: Resolve solve(1, 2) = 1 + min(0, 0) = 1.

Step 11: Resolve solve(1, 3) = 1 + min(solve(2,3), solve(1,2)) = 1 + min(1, 1) = 2.

Step 12: Resolve solve(0, 4) = solve(1, 3) = 2. The answer is 2 insertions.

Recursive Exploration of All Insertion Choices — Watch how the recursion branches at each mismatch and collapses back with results. Notice solve(2,2) is computed twice — an overlapping subproblem.

Algorithm

  1. Define a recursive function solve(l, h) that returns the minimum insertions to make s[l..h] a palindrome.
  2. Base case: If l >= h, return 0 (empty or single character is already a palindrome).
  3. Match: If s[l] == s[h], the outermost characters mirror each other. Return solve(l+1, h-1).
  4. Mismatch: If s[l] != s[h], insert a character to fix one end. Return 1 + min(solve(l+1, h), solve(l, h-1)).
  5. Call solve(0, n-1) to get the answer.

Code

class Solution {
public:
    int minInsertions(string s) {
        return solve(s, 0, s.size() - 1);
    }

private:
    int solve(string& s, int l, int h) {
        if (l >= h) return 0;
        if (s[l] == s[h]) return solve(s, l + 1, h - 1);
        return min(solve(s, l + 1, h), solve(s, l, h - 1)) + 1;
    }
};
class Solution:
    def minInsertions(self, s: str) -> int:
        def solve(l: int, h: int) -> int:
            if l >= h:
                return 0
            if s[l] == s[h]:
                return solve(l + 1, h - 1)
            return min(solve(l + 1, h), solve(l, h - 1)) + 1

        return solve(0, len(s) - 1)
class Solution {
    public int minInsertions(String s) {
        return solve(s, 0, s.length() - 1);
    }

    private int solve(String s, int l, int h) {
        if (l >= h) return 0;
        if (s.charAt(l) == s.charAt(h)) return solve(s, l + 1, h - 1);
        return Math.min(solve(s, l + 1, h), solve(s, l, h - 1)) + 1;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each mismatch, the recursion branches into two calls. In the worst case (all characters are different), nearly every call branches, producing an exponential recursion tree. The number of unique subproblems is only O(n²) — defined by the two parameters l and h — but without memoization, the same subproblems are recomputed many times.

Space Complexity: O(n)

The space is dominated by the recursion call stack. The maximum recursion depth is n (when we shrink the substring by one character per call), so the stack uses O(n) space.

Why This Approach Is Not Efficient

The brute force recursion has O(2^n) time complexity because every mismatch doubles the number of recursive calls, yet the total number of distinct subproblems is only O(n²). This means the recursion tree contains a massive amount of redundant computation — the same substring pairs (l, h) are solved over and over.

For a string of length 500 (the maximum constraint), 2^500 is astronomically large — far beyond any time limit. Even for moderately sized strings, the exponential blowup makes this approach impractical.

The key insight: Since there are only O(n²) unique subproblems (each defined by a pair of indices l and h where 0 ≤ l ≤ h < n), we can store the result of each subproblem the first time we compute it and reuse it whenever it's needed again. This is the principle of Dynamic Programming, and it reduces the time from O(2^n) to O(n²).

Better Approach - Interval Dynamic Programming

Intuition

Instead of recomputing the same subproblems, we can build a 2D table dp[l][h] where each cell stores the minimum insertions needed for the substring s[l..h]. We fill this table bottom-up, starting from the smallest substrings (length 1) and building up to the full string.

Think of it like building a pyramid of knowledge:

  • Foundation (length 1): Every single character is a palindrome — 0 insertions needed.
  • Next layer (length 2): For each pair of adjacent characters, check if they match (0 insertions) or not (1 insertion).
  • Growing upward (length 3, 4, ...): For each longer substring, use the answers from shorter substrings that we already computed.

By filling the table from small substrings to large ones, every cell only depends on cells that are already filled. This eliminates all redundant computation and turns the O(2^n) recursion into an O(n²) systematic table fill.

Step-by-Step Explanation

Let's trace through filling the DP table for s = "mbadm" (indices 0 through 4).

The table dp[l][h] stores the minimum insertions for s[l..h]. We fill by increasing substring length.

Step 1: Length 1 (Diagonal — Base Cases)

  • dp[0][0] = dp[1][1] = dp[2][2] = dp[3][3] = dp[4][4] = 0
  • Every single character is already a palindrome.

Step 2: Length 2 — dp[3][4]

  • s[3]='d' ≠ s[4]='m' → min(dp[4][4], dp[3][3]) + 1 = min(0, 0) + 1 = 1

Step 3: Length 2 — dp[2][3]

  • s[2]='a' ≠ s[3]='d' → min(dp[3][3], dp[2][2]) + 1 = 1

Step 4: Length 2 — dp[1][2]

  • s[1]='b' ≠ s[2]='a' → min(dp[2][2], dp[1][1]) + 1 = 1

Step 5: Length 2 — dp[0][1]

  • s[0]='m' ≠ s[1]='b' → min(dp[1][1], dp[0][0]) + 1 = 1

Step 6: Length 3 — dp[2][4]

  • s[2]='a' ≠ s[4]='m' → min(dp[3][4], dp[2][3]) + 1 = min(1, 1) + 1 = 2

Step 7: Length 3 — dp[1][3]

  • s[1]='b' ≠ s[3]='d' → min(dp[2][3], dp[1][2]) + 1 = min(1, 1) + 1 = 2

Step 8: Length 3 — dp[0][2]

  • s[0]='m' ≠ s[2]='a' → min(dp[1][2], dp[0][1]) + 1 = min(1, 1) + 1 = 2

Step 9: Length 4 — dp[1][4]

  • s[1]='b' ≠ s[4]='m' → min(dp[2][4], dp[1][3]) + 1 = min(2, 2) + 1 = 3

Step 10: Length 4 — dp[0][3]

  • s[0]='m' ≠ s[3]='d' → min(dp[1][3], dp[0][2]) + 1 = min(2, 2) + 1 = 3

Step 11: Length 5 — dp[0][4] (Full String!)

  • s[0]='m' == s[4]='m' → Characters match! dp[0][4] = dp[1][3] = 2
  • The outer 'm's mirror each other naturally, so we just need the inner answer.

Result: dp[0][4] = 2.

Interval DP Table — Building from Small Substrings to Full String — Watch the DP table fill diagonally from length-1 substrings up to the full string. Each cell dp[l][h] uses results from already-computed shorter substrings.

Algorithm

  1. Create a 2D table dp of size n×n, initialized to 0.
  2. The diagonal dp[i][i] = 0 is the base case (single characters).
  3. Fill the table by increasing substring length (from 2 to n):
    • For each starting index l, compute ending index h = l + length - 1.
    • If s[l] == s[h]: dp[l][h] = dp[l+1][h-1] (endpoints match, use inner substring's answer).
    • If s[l] != s[h]: dp[l][h] = min(dp[l+1][h], dp[l][h-1]) + 1 (try skipping either end, plus 1 insertion).
  4. Return dp[0][n-1] — the answer for the full string.

Code

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int len = 2; len <= n; len++) {
            for (int l = 0; l <= n - len; l++) {
                int h = l + len - 1;
                if (s[l] == s[h]) {
                    dp[l][h] = dp[l + 1][h - 1];
                } else {
                    dp[l][h] = min(dp[l + 1][h], dp[l][h - 1]) + 1;
                }
            }
        }

        return dp[0][n - 1];
    }
};
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for length in range(2, n + 1):
            for l in range(n - length + 1):
                h = l + length - 1
                if s[l] == s[h]:
                    dp[l][h] = dp[l + 1][h - 1]
                else:
                    dp[l][h] = min(dp[l + 1][h], dp[l][h - 1]) + 1

        return 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 l = 0; l <= n - len; l++) {
                int h = l + len - 1;
                if (s.charAt(l) == s.charAt(h)) {
                    dp[l][h] = dp[l + 1][h - 1];
                } else {
                    dp[l][h] = Math.min(dp[l + 1][h], dp[l][h - 1]) + 1;
                }
            }
        }

        return dp[0][n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n²)

We fill a 2D table of size n×n. Specifically, we fill the upper triangle, which has n·(n+1)/2 cells. Each cell is computed in O(1) time using previously filled cells. Total: O(n²).

Space Complexity: O(n²)

The 2D DP table dp[n][n] requires O(n²) space. For n = 500, this is 250,000 entries — feasible but uses significant memory.

Why This Approach Is Not Efficient

The interval DP approach runs in O(n²) time, which is perfectly acceptable for n ≤ 500 (at most 250,000 operations). However, it uses O(n²) space for the 2D table, which can be wasteful.

More importantly, there is a more elegant formulation of this problem. The key insight is:

Minimum insertions to make a string palindrome = n − length of the Longest Palindromic Subsequence (LPS)

Why? The LPS is the longest part of the string that already reads the same forwards and backwards (as a subsequence). The remaining characters — all n - LPS of them — each need exactly one insertion to create their mirror counterpart in the palindrome.

Furthermore, computing LPS can be reduced to a standard Longest Common Subsequence (LCS) problem: LPS(s) = LCS(s, reverse(s)). The LCS approach not only provides an elegant reduction to a well-known problem, but also enables space optimization from O(n²) to O(n) — since standard LCS tabulation only needs the previous row to compute the current row.

Optimal Approach - Longest Palindromic Subsequence via LCS

Intuition

The breakthrough idea rests on a beautiful connection between three concepts:

  1. Minimum insertions to make a palindrome — what we want to find.
  2. Longest Palindromic Subsequence (LPS) — the longest subsequence of s that is itself a palindrome.
  3. Longest Common Subsequence (LCS) — the classic DP problem of finding the longest sequence common to two strings.

Here is how they connect:

Claim: min_insertions(s) = n - LPS(s)

Why? The LPS identifies the maximum number of characters already in palindromic order. These characters form the "skeleton" of the final palindrome — they stay in place. Every character NOT in the LPS needs a mirror partner inserted. So we need exactly n - LPS(s) insertions.

Claim: LPS(s) = LCS(s, reverse(s))

Why? A palindromic subsequence reads the same forwards and backwards. If we reverse the string, that same subsequence still appears (in the same order). So a palindromic subsequence of s is exactly a common subsequence of s and reverse(s). The longest one is the LPS.

For s = "mbadm", the reverse is "mdabm". The LCS of "mbadm" and "mdabm" is "mam" (length 3). So LPS = 3, and the answer is 5 - 3 = 2.

The huge advantage: we can compute LCS with only two rows at a time (current and previous), reducing space from O(n²) to O(n).

Diagram showing the connection between the original string mbadm, its reverse mdabm, and how LCS gives the Longest Palindromic Subsequence
Diagram showing the connection between the original string mbadm, its reverse mdabm, and how LCS gives the Longest Palindromic Subsequence

Step-by-Step Explanation

Let's trace through with s = "mbadm", rev = "mdabm".

We build the LCS table where dp[i][j] = length of LCS of s[0..i-1] and rev[0..j-1].

Step 1: Initialize: first row and column are all 0 (empty string has LCS 0 with anything).

Step 2: Fill dp[1][1]: s[0]='m' == rev[0]='m' → Match! dp[1][1] = dp[0][0] + 1 = 1.

Step 3: Fill dp[1][2]: s[0]='m' ≠ rev[1]='d' → No match. dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1. Complete row 1: [0, 1, 1, 1, 1, 1].

Step 4: Fill dp[2][4]: s[1]='b' == rev[3]='b' → Match! dp[2][4] = dp[1][3] + 1 = 1 + 1 = 2. LCS grows to 2!

Step 5: Complete row 2: [0, 1, 1, 1, 2, 2].

Step 6: Fill dp[3][3]: s[2]='a' == rev[2]='a' → Match! dp[3][3] = dp[2][2] + 1 = 1 + 1 = 2.

Step 7: Complete row 3: [0, 1, 1, 2, 2, 2].

Step 8: Fill dp[4][2]: s[3]='d' == rev[1]='d' → Match! dp[4][2] = dp[3][1] + 1 = 1 + 1 = 2.

Step 9: Complete row 4: [0, 1, 2, 2, 2, 2].

Step 10: Fill dp[5][5]: s[4]='m' == rev[4]='m' → Match! dp[5][5] = dp[4][4] + 1 = 2 + 1 = 3. LCS = 3!

Step 11: Complete row 5: [0, 1, 2, 2, 2, 3].

Result: LCS = dp[5][5] = 3. LPS length = 3. Minimum insertions = 5 − 3 = 2.

LCS Table — Finding the Longest Palindromic Subsequence — Watch the LCS table fill row by row for s='mbadm' and rev='mdabm'. Each match cell increments the LCS length. The final cell gives LPS, and n minus LPS gives our answer.

Algorithm

  1. Reverse the string s to get rev.
  2. Compute LCS(s, rev) using space-optimized tabulation:
    • Maintain two arrays: prev and curr, each of size n + 1.
    • For each character s[i-1] (row i):
      • For each character rev[j-1] (column j):
        • If s[i-1] == rev[j-1]: curr[j] = prev[j-1] + 1 (extend the match).
        • Else: curr[j] = max(prev[j], curr[j-1]) (take the better of skipping either character).
      • After processing the row, set prev = curr.
  3. The LCS length is prev[n]. This equals the LPS length.
  4. Return n - prev[n] — the minimum number of insertions.

Code

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        string rev(s.rbegin(), s.rend());

        vector<int> prev(n + 1, 0);

        for (int i = 1; i <= n; i++) {
            vector<int> curr(n + 1, 0);
            for (int j = 1; j <= n; j++) {
                if (s[i - 1] == rev[j - 1]) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = max(prev[j], curr[j - 1]);
                }
            }
            prev = curr;
        }

        return n - prev[n];
    }
};
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        rev = s[::-1]

        prev = [0] * (n + 1)

        for i in range(1, n + 1):
            curr = [0] * (n + 1)
            for j in range(1, n + 1):
                if s[i - 1] == rev[j - 1]:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev = curr

        return n - prev[n]
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();

        int[] prev = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int[] curr = new int[n + 1];
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == rev.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            prev = curr;
        }

        return n - prev[n];
    }
}

Complexity Analysis

Time Complexity: O(n²)

We compute the LCS of two strings of length n, which requires filling an n×n table. Each cell is computed in O(1) time. Total: O(n²). For n = 500, this is 250,000 operations — very fast.

Space Complexity: O(n)

Instead of storing the full n×n LCS table, we use the space-optimized approach with only two arrays of size n+1 (prev and curr). Since each row only depends on the previous row, we don't need to keep older rows. This reduces space from O(n²) to O(n), a significant improvement for large inputs.

This is the best we can achieve: the problem inherently requires examining O(n²) character pairs (since any pair of positions could contribute to the LPS), so O(n²) time is a natural lower bound. The O(n) space is optimal for this approach.