Fewest Letters to Mirror
Medium2-D Dynamic Programming
Problem
A sign maker wants every banner to read the same forwards and backwards. Given a lowercase string s, you may insert any letters at any positions.
Return the minimum number of insertions needed to turn s into a palindrome.
Example 1
- Input:
- s = "abca"
- Output:
- 1
Insert "b" after "c" to get "abcba" (or "c" after "a" to get "acbca").
Example 2
- Input:
- s = "race"
- Output:
- 3
"ecarace" needs three new letters; two are not enough.
Example 3
- Input:
- s = "level"
- Output:
- 0
Constraints
- 1 ≤ s.length ≤ 500
- s consists of lowercase English letters.
Hint
Show the first hint
Look at the first and last characters. When they match, what is left to fix?
Walkthrough
How to approach it
01Clarify before coding
- Are only insertions allowed? Yes, no deletions or replacements.
- Do we return the count or the palindrome? Only the count.
- Is an already-palindromic string 0? Yes.
02Brute force
Try every way of inserting characters, breadth-first by number of insertions, until a palindrome appears.
Cost: Exponential in the answer and the string length: unusable for 500 characters.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.