Minimum Insertions to Make String Palindrome
Minimum Insertion Steps To Make A String Palindrome: fewest character insertions anywhere to make s a palindrome.
- 1 <= s.length <= 500
- s consists of lowercase English letters.
Intuition
The problem of minimum insertions to make string palindrome asks for the fewest characters you can insert anywhere in a string so that the result reads the same both ways. Searching over possible insertions directly is hopeless — there are too many positions and too many choices.
Invert the question. Instead of asking what to insert, ask what you get to keep. Every character in the final palindrome either came from the original string or was inserted. Characters that already form a palindromic pattern can stay exactly where they are; every other character needs a matching partner inserted on the opposite side to balance it.
That gives a precise accounting:
- Each character you keep costs nothing, and each one you cannot keep costs exactly one insertion.
So minimising insertions means maximising what stays, and the largest set of characters that can stay — in order, forming a palindrome — is the longest palindromic subsequence. The answer is n − LPS(s).
That still leaves computing the LPS, and there is a neat reduction for it. A subsequence common to both s and its reverse must read identically forwards and backwards, which is what a palindrome is. So LPS(s) = LCS(s, reverse(s)), and the longest common subsequence is a standard two-dimensional DP table you may already know how to fill.
The reframing is everything: characters already forming a palindromic subsequence never need a partner inserted, so the answer is n − LPS. And the longest palindromic subsequence of s is just the LCS of s with its own reverse. Two substitutions turn an unfamiliar question into one you've already solved — always ask what the untouched part of the answer looks like.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n²) time and O(n²) space.
Reframe insertions as characters kept
Every character either survives into the final palindrome or needs a mirror partner inserted. Minimising insertions is therefore the same as maximising kept characters, which converts a search over insertions into a search over subsequences.
Identify what can be kept as the LPS
The characters that can stay, in their original order, forming a palindrome, are exactly the longest palindromic subsequence. Everything not in it costs one insertion each, so the answer is n - LPS.
Reduce LPS to LCS with the reversed string
A subsequence appearing in both s and reverse(s) reads the same in both directions — it is palindromic. So LPS(s) = LCS(s, reverse(s)), turning an unfamiliar problem into the standard LCS table rather than requiring a new recurrence.
Fill the LCS table
Let dp[i][j] be the LCS of the first i characters of s and the first j of its reverse. When the characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise take max(dp[i-1][j], dp[i][j-1]). Fill row by row from the empty-prefix base cases of zero.
Subtract to get the answer
The result is n - dp[n][n]. Returning the LCS value itself is the easy mistake here — that is the number of characters kept, not the number of insertions needed.
Cost of the table
The table has n² cells and each is filled in O(1), giving O(n²) time and O(n²) space. Space drops to O(n) by keeping only the previous row, since each cell depends solely on the row above and the cell to its left — worth mentioning when the string is long.
Solution & live demo
Common pitfalls
Comparing the string against itself
t = s
t = s[::-1]
The LCS of a string with itself is the whole string, so the answer collapses to 0 for every input. Palindromic structure is revealed by matching the string against its reverse — that's what pairs the first character with the last.
Returning the LCS length itself
return dp[n][n]
return n - dp[n][n]
dp[n][n] counts the characters that already pair up. What the question asks for is the ones that don't — every unmatched character needs a mirror inserted.
Assuming it needs a separate palindrome DP
# a bespoke dp[i][j] over substrings of s
# reuse the LCS table on s and reversed(s)
A two-pointer interval DP also works, but it's a second recurrence to get right. Recognising this as LCS in disguise lets you reuse code you already trust.
Edge cases
LPS = n → 0 insertions.
LPS = 1 → n−1 insertions.