Minimum Insertions to Make String Palindrome
Hard · Dynamic Programming · String · Dynamic Programming
Problem
Given a string s, one step inserts any character at any position.
Return the minimum number of steps needed to turn s into a palindrome (a string that reads the same forwards and backwards).
Examples
Input: s = "abcb" Output: 1
Append "a" to get "abcba".
Input: s = "race" Output: 3
No two letters can face each other, so three of the four need a mirror: "ecarace".
Input: s = "noon" Output: 0
Already a palindrome.
Constraints
- 1 <= len(s) <= 500
- s consists of lowercase English letters.
Approaches
- Longest palindromic subsequence, full table — time O(n^2), space O(n^2)
Follow-up
The same table answers "fewest deletions to make a palindrome" (it is the same number). The use cases restrict insertions to the front (then only a palindromic prefix can stay, found in linear time) and put a price on each inserted letter.
Related problems
Start free on Cariara · Coding problems · System design studio
