Fewest Mirror Cuts
Problem
A banner reads s. You may cut it into consecutive pieces, and every piece must read the same forwards and backwards (a mirror piece).
Return the minimum number of cuts needed.
Example 1
- Input:
- s = "aabcb"
- Output:
- 1
"aa" | "bcb".
Example 2
- Input:
- s = "abc"
- Output:
- 2
"a" | "b" | "c".
Example 3
- Input:
- s = "racecar"
- Output:
- 0
Already a mirror.
Constraints
- 1 ≤ s.length ≤ 2000
- s contains lowercase English letters.
Hint
Show the first hint
Let cuts[i] = fewest cuts for the prefix s[0..i]. What does its LAST piece look like?
Walkthrough
How to approach it
01Clarify before coding
- Cuts or pieces? Cuts: pieces minus one, so a mirror string needs 0.
- Single letters are mirrors? Yes, so n - 1 cuts always works.
- n up to 2000: an O(n³) check of every piece is too slow, O(n²) is the target.
02Brute force
Recursively try every mirror prefix as the first piece and recurse on the rest, checking each candidate by reversal.
Cost: Exponential without memoization; even memoized with naive mirror checks it is O(n³) ≈ 8·10^9 at n = 2000.
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.