833. Strange Printer (Recursive Interval DP)

Return min turns to print string s with a strange printer (overwrites any contiguous range).

Input: Quoted string.

Output: Integer.

Examples

Example 1

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

Example 2

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

Example 3

Input: "a"
Output: 1
Explanation: One char.