Minimum Insertions to Make String Palindrome
Fewest character insertions anywhere to make s a palindrome.
02
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.
03
Approach
1
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.
2
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.
3
Standard LCS table
dp[i][j] = LCS of prefixes; match → diagonal+1, else max of neighbours. Answer n − dp[n][n].
04
Solution & live demo
python
▶1class Solution:
▶2 def minInsertions(self, s):
▶3 t = s[::-1]
▶4 n = len(s)
▶5 dp = [[0] * (n + 1) for _ in range(n + 1)]
▶6 for i in range(1, n + 1):
▶7 for j in range(1, n + 1):
▶8 if s[i-1] == t[j-1]:
▶9 dp[i][j] = dp[i-1][j-1] + 1
▶10 else:
▶11 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
▶12 return n - dp[n][n]
05
Edge cases
Already a palindrome
LPS = n → 0 insertions.
All distinct characters
LPS = 1 → n−1 insertions.
06
Complexity
Time
O(n²)
Space
O(n²)
Rollable to O(n) space with two rows.