The Strange Printer

A strange printer works in turns. In each turn it picks one letter and a stretch of consecutive positions on the page, and prints that letter at every position of the stretch, covering whatever was printed there before. The page starts blank.

Write fewest_turns(s) that returns the fewest turns the printer needs to produce the string s exactly.

Examples

fewest_turns("aaabbb")  # returns 2
fewest_turns("aba")     # returns 2
fewest_turns("abcabc")  # returns 5
fewest_turns("")        # returns 0

For "aba", print "aaa" first, then a "b" over the middle position.

Constraints

• 0 <= len(s) <= 100
• s holds lowercase letters only.