147. Strange Printer (Array Encoding)

A strange printer prints a string by printing a sequence of the same character starting and ending anywhere, overwriting existing characters. Return the minimum number of turns to print the given string. Input: a quoted string.

Input: A quoted string.

Output: Integer — minimum print turns.

Examples

Input: "aaabbb"
Output: 2
Explanation: Print 'aaa' then 'bbb'.

Input: "aba"
Output: 2
Explanation: Print 'aaa' then overwrite middle with 'b'.

Input: "a"
Output: 1
Explanation: Single turn.

Constraints

• 0<=s.length<=100

Asked by