Description
A strange printer can only print a sequence of the same character at a time and can print new characters starting from any place. Return the minimum number of turns to print string s.
Examples
Input:
s = "aaabbb"Output:
2Explanation:
Print 'aaa' in turn 1 (positions 0-2), then 'bbb' in turn 2 (positions 3-5). Two distinct runs = 2 turns.
Input:
s = "abcabc"Output:
5Explanation:
5 distinct character groups: a,b,c,a,b,c. DP finds no overlapping pattern to reduce turns. Minimum: 5 turns.
Input:
s = "ababa"Output:
3Explanation:
Print 'aaa' at 0,2,4, then 'b' at 1, then 'b' at 3. Or: 'aaaaa', overwrite 1,3 with 'b'. Either way: 3 turns.
Constraints
- •
1 ≤ s.length ≤ 100 - •
s consists of lowercase English letters.