Clear the Shelf by Palindromes
Problem
A shelf holds a row of jars labelled with integers labels. In one move you may remove any contiguous group of jars whose labels read the same forwards and backwards (a single jar always qualifies). The jars on either side then close the gap.
Return the minimum number of moves needed to clear the whole shelf.
Example 1
- Input:
- labels = [1, 3, 2, 3, 1]
- Output:
- 1
The whole row is already a palindrome.
Example 2
- Input:
- labels = [4, 1, 4, 2]
- Output:
- 2
Remove [4, 1, 4], then [2]. Removing [1] first would leave [4, 4, 2], which also takes two more moves.
Example 3
- Input:
- labels = [1, 2, 1, 1, 3, 1]
- Output:
- 2
Remove [1, 2, 1]; the shelf becomes [1, 3, 1], removed in one move.
Constraints
- 1 ≤ labels.length ≤ 100
- 1 ≤ labels[i] ≤ 20
Hint
Show the first hint
Focus on the leftmost jar of a stretch. Either it is removed on its own, or together with some later jar that has the same label.
Walkthrough
How to approach it
01Clarify before coding
- Is a single jar a palindrome? Yes, so the answer is at most n.
- Do removed gaps close so new palindromes can form? Yes, that is the whole difficulty.
- Is the label range relevant? Only for equality; values never add up.
02Brute force
Breadth-first search over shelf states: from each row, try removing every palindromic substring.
Cost: The number of reachable rows is exponential in n.
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.