Minimum Insertion Steps to Make a String Palindrome

LeetCode 1312, Minimum Insertion Steps to Make a String Palindrome, asks you to return the minimum number of character insertions needed to make a string s a palindrome. You can insert any character at any position. For example, "mbadm" needs 2 insertions to become "mbdadbm", and "leetcode" needs 5.

This is a hard problem, but the core idea is surprisingly elegant once you see the connection to palindromic subsequences.

Why this problem matters

This is a classic DP problem that reduces to finding the longest palindromic subsequence (LPS). The reduction is beautiful: the minimum number of insertions equals len(s) - LPS(s). If you already know the longest palindromic subsequence, the characters not in that subsequence each need a mirror character inserted. Understanding this connection is a gateway to many other DP string problems, including edit distance, longest common subsequence, and palindrome partitioning.

The key insight

Think about what happens when you make a string into a palindrome by inserting characters. The characters you do not touch must already form a palindromic subsequence in the original string. The longer that subsequence is, the fewer insertions you need.

So the minimum number of insertions is len(s) - LPS(s).

How do you find the LPS? You can compute it directly with interval DP on substrings, or you can use a neat trick: the longest palindromic subsequence of s is the same as the longest common subsequence (LCS) of s and reverse(s). A subsequence that reads the same forward and backward is, by definition, common to both s and its reverse.

This means the problem reduces to a standard LCS computation, which you may already know from other problems.

The solution

def min_insertions(s):
    n = len(s)
    rev = 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 rev[i - 1] == s[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]

We create rev, the reverse of s, and build a 2D DP table where dp[i][j] is the length of the LCS of rev[0..i-1] and s[0..j-1]. When characters match, we extend the subsequence from the diagonal. When they do not match, we take the best of skipping one character from either string. The final answer is n - dp[n][n], subtracting the LPS length from the total string length.

Visual walkthrough

Let's trace the algorithm on s = "mbadm" with reverse(s) = "mdabm". We build the LCS table row by row.

The final cell dp[5][5] = 3 tells us the LPS has length 3. One such LPS is "mam". The minimum insertions are 5 - 3 = 2. We need to insert mirror characters for "b" and "d" to produce a palindrome like "mbdadbm".

Complexity analysis

Both approaches run in O(n^2) time and O(n^2) space. The LCS approach builds a table of size (n+1) x (n+1). The interval DP approach builds a table indexed by substring start and end. They are equivalent in complexity.

You can optimize space to O(n) by observing that each row of the DP table only depends on the previous row. Keep two rows (or a single row updated carefully) instead of the full table. This does not change the time complexity but reduces memory from O(n^2) to O(n).

The building blocks

1. Longest palindromic subsequence

The LPS is the core subproblem. You can compute it directly with interval DP:

def lps(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

Here dp[i][j] represents the LPS length for the substring s[i..j]. For a single character, the LPS is 1. For a range, if the endpoints match, they both belong to the LPS and we add 2 to the inner subproblem. If they do not match, we drop one endpoint and take the better result.

2. Interval DP / LCS reduction

The LCS reduction avoids thinking about intervals entirely:

def lps_via_lcs(s):
    rev = s[::-1]
    n = len(s)
    prev = [0] * (n + 1)

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

    return prev[n]

This is the space-optimized version using only two rows. The logic is the same LCS recurrence, but instead of storing the entire table, we keep prev (the previous row) and curr (the current row). After processing all rows, prev[n] holds the LPS length.

Edge cases

• Already a palindrome. If s is already a palindrome, the LPS equals the full string, so the answer is 0. Examples: "aba", "a", "abcba".
• Single character. Always a palindrome. Answer is 0.
• All same characters. "aaaa" is already a palindrome. Answer is 0.
• Two characters. If both are the same, answer is 0. If different (like "ab"), the LPS is 1, so you need 1 insertion.
• Completely distinct characters. "abcde" has LPS of length 1. You need n - 1 insertions.

From understanding to recall

The key fact to remember is the reduction: minimum insertions = len(s) - LPS(s). That single line connects this problem to the entire family of LCS/LPS problems. If you can write the LCS recurrence from memory, you can solve this problem in under five minutes.

The tricky part is not the code itself but remembering that the reduction exists. When you see "make a string palindrome" in an interview, the reflex should be: find the longest palindromic subsequence, subtract from the length. Drilling this connection until it becomes automatic is what separates recognition from recall.

Related posts

• Longest Palindromic Substring - Finding palindromic structure within strings
• Edit Distance - Another classic DP problem with string transformation
• Longest Common Subsequence - The LCS technique used in the reduction

Once you have the LCS building block locked in, problems like this one become assembly rather than invention. You recognize the pattern, apply the reduction, and write the solution. That is the power of drilling fundamentals.