Mirrored Chunks
HardTwo Pointers
Problem
Split a string text into consecutive non-empty chunks c1, c2, …, cm so that the sequence of chunks reads the same from both ends: c1 = cm, c2 = c(m-1), and so on (a middle chunk, if m is odd, pairs with itself).
Return the largest possible number of chunks m.
Example 1
- Input:
- text = "volvo"
- Output:
- 3
"vo" | "l" | "vo".
Example 2
- Input:
- text = "abcxyzabc"
- Output:
- 3
"abc" | "xyz" | "abc".
Example 3
- Input:
- text = "merchant"
- Output:
- 1
No prefix equals the suffix of the same length, so the whole string is one chunk.
Constraints
- 1 ≤ text.length ≤ 1000
- text consists of lowercase English letters
Hint
Show the first hint
The first chunk must equal the last chunk. Which lengths are possible for them?
Walkthrough
How to approach it
01Clarify before coding
- Is a single chunk (the whole string) always valid? Yes, so the answer is at least 1.
- Must the chunks be contiguous and cover the whole string? Yes.
- Can the middle chunk be any string? Yes, it only has to equal itself.
02Brute force
Recursively try every matching prefix/suffix length L, recurse on the middle and keep the best count.
Cost: Exponential without memoisation; O(n³) with memoisation over (start, end) and substring comparisons.
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.