Problem
Return the fewest characters that must be inserted into a string to make it a palindrome. Existing characters keep their order.
Worked examples
Input: s = "abc"
Output: 2
Insert two characters to obtain "abcba".
Hints
Hint 1
Think about the two ends of a substring.
Hint 2
Matching ends leave the inner substring; mismatched ends require one insertion.
Solution approach
- Let dp[i][j] be the minimum insertions for s[i..j]. Single characters need zero.
- If the ends match, use dp[i+1][j-1]. Otherwise use 1 + min(dp[i+1][j], dp[i][j-1]).
- Fill shorter intervals before longer intervals. Return dp[0][n-1].
Complexity
O(n²) time and O(n²) space; one-dimensional DP reduces space to O(n).
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗