One-Letter Roller

Hard

A label printer works in an unusual way: in a single pass its roller prints a run of one repeated letter. A pass can start and end anywhere on the tape, and the new letters cover whatever was printed there before. The tape starts blank and must end up holding exactly the string text. Return the smallest number of passes that is enough to do this.

Example 1

text='abba' → 2

First the roller covers the whole tape with a, giving aaaa, then a second pass prints bb in the middle.

Example 2

text='tattoo' → 3

For example: tttt over the first four places, then a at the second place and oo at the end, three passes in total. You cannot do better: the word has three different letters, and each needs at least one pass.

Constraints

1 ≤ text.length ≤ 200
text consists of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

text='abba'

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.