Minimum Insertion Steps to Make a String Palindrome

Minimum Insertion Steps to Make a String Palindrome looks like a string-editing puzzle, but it is really a disguised longest common subsequence problem. The trick is to notice what you are allowed to keep.

The slow way first

You could try every possible set of insertions and look for the cheapest one that produces a palindrome. The number of ways to splice characters in explodes exponentially, so brute force is hopeless even for short strings.

The question to ask: which characters do I get to keep untouched? The characters I never have to mirror are exactly the ones that already form a palindrome inside s — its longest palindromic subsequence (LPS). Everything outside that core needs a matching insertion.

The idea: LPS equals LCS with the reverse

A palindromic subsequence reads the same in s and in reverse(s). So the longest palindromic subsequence of s is just the longest common subsequence of s and reverse(s). We already know how to compute LCS with a DP grid, and the final answer is n - LPS.

Each cell dp[i][j] holds the LCS length of the first i letters of s and the first j letters of rev. If the two current letters match, we extend the diagonal by one; otherwise we carry the larger of the two neighbors.

Walk through it

Step through the animation. The grid fills row by row. When s[i-1] and rev[j-1] match, the cell turns green and takes dp[i-1][j-1] + 1. When they differ, it takes the larger neighbor. The bottom-right cell ends at 3 — the LPS "aca" — so the answer is 4 − 3 = 1.

Pseudocode

rev = s reversed
n = length of s
make an (n+1) x (n+1) grid dp filled with 0
for i from 1 to n:
    for j from 1 to n:
        if s[i-1] == rev[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1      # letters match, extend diagonal
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # carry larger neighbor
lps = dp[n][n]                                # longest palindromic subsequence
return n - lps                                # letters needing a mirror insertion

The Python solution

def min_insertions(s):
    rev = s[::-1]
    n = len(s)
    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] == rev[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    lps = dp[n][n]
    return n - lps

• rev = s[::-1] reverses the string; LPS of s is the LCS of s and rev.
• dp is an (n+1) x (n+1) grid; row 0 and column 0 stay 0 because an empty prefix shares nothing.
• When s[i-1] == rev[j-1] the letters line up, so we add one to the diagonal predecessor dp[i-1][j-1].
• When they differ we drop one letter from either side and keep the better result, max(dp[i-1][j], dp[i][j-1]).
• dp[n][n] is the LPS length; n - lps counts the letters that have no partner and thus need an insertion.

Complexity

The grid has n² cells and each is computed in constant time, giving O(n²) time. The full table costs O(n²) space; you can shrink it to two rows for O(n) space if needed.

When this pattern shows up

Practice