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' then 'bbb'.
Input:
s = "abcabc"Output:
4Explanation:
First print 'aaaaaa', then overprint positions 2-4 with 'bbb', then overprint positions 3 with 'c', then overprint position 6 with 'c'. This demonstrates how the printer can overwrite characters and how repeated patterns still require multiple operations.
Input:
s = "ababa"Output:
3Explanation:
First print 'aaaaa' (covering all positions), then overprint positions 2 and 4 with 'bb', then overprint position 4 with 'a' again. This shows how alternating characters require strategic overprinting to minimize turns.
Constraints
- •
1 ≤ s.length ≤ 100 - •
s consists of lowercase English letters.