Minimum Insertions to Make String Palindrome
Fewest character insertions anywhere to make s a palindrome.
Intuition
Characters already forming a palindromic subsequence can stay put; everything else needs a mirror partner inserted. The longest palindromic subsequence (LPS) is what you keep, and LPS(s) = LCS(s, reverse(s)). Answer: n − LPS.
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
Reduce to keep-vs-insert
Each kept character pairs with itself in the final palindrome; each unkept one costs exactly one insertion. Maximize kept = LPS.
LPS via LCS with the reverse
A common subsequence of s and reversed s reads the same forwards and backwards — it's a palindromic subsequence.
Standard LCS table
dp[i][j] = LCS of prefixes; match → diagonal+1, else max of neighbours. Answer n − dp[n][n].
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.