A row of fridge magnets spells the string board. In one lift a child takes off a contiguous group of magnets (one magnet or more) that reads the same forwards and backwards. The magnets on either side then slide together, so letters that were far apart can become neighbours for later lifts.
Return the fewest lifts needed to clear the whole board. An empty board needs 0 lifts.
Examples
Input: board = "abca"
Output: 2
Explanation: lift "b" to get "aca", then lift "aca".
Input: board = "abcba"
Output: 1
Input: board = "abcab"
Output: 3
Constraints
0 <= len(board) <= 200boardcontains lowercase letters only
Goals
- Model removals that make far-apart letters become neighbours
- Pair the first letter of a stretch with a matching later letter
- Handle the two-letter and one-letter palindromes as base cases