Strange Printer Turns Problem

Strange Printer Turns Problem — ExecCode Hard DSA Practice

Solve the Strange Printer Turns problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A printer that in one turn paints a contiguous substring to the same character (overwriting). Start from an empty string (conceptually unpainted). Compute the fewest turns to obtain s. Interval DP: printing a character can cover later equal characters 'for free' if they sit in the same paint. Return the minimum number of turns. You are given: s — lowercase string Return integer >= 1 for non-empty s. A string of all equal letters needs 1 turn.

Examples

Input {'s': 'aaabbb'}; Output 2. Input {'s': 'aba'}; Output 2. Input {'s': 'abc'}; Output 3

Constraints

Overwriting is allowed A turn must paint a contiguous segment one character

Practice Strange Printer Turns free on ExecCode. Browse DSA problems, topic map, and placement guides.