A decorator paints a strip of tiles that starts out blank. In one pass her roller paints a contiguous run of tiles (one tile or more) in a single colour, covering whatever colours those tiles had before. The finished strip must show the colours in the string strip, one lowercase letter per tile.
Return the fewest passes needed. An empty strip needs 0 passes.
Examples
Input: strip = "aba"
Output: 2
Explanation: paint all three tiles 'a', then paint the middle tile 'b'.
Input: strip = "abcabc"
Output: 5
Input: strip = "aaabbb"
Output: 2
Constraints
0 <= len(strip) <= 200stripcontains lowercase letters only
Goals
- Find the interval recurrence when later strokes may cover earlier ones
- Let the first tile's stroke stretch to a later tile of the same colour
- Collapse runs of equal letters before filling the table