Shortest Run Code

Hard

A string is compressed like this: every run of two or more equal letters in a row is replaced by the letter followed by the length of the run, while single letters stay as they are. For example, aabccc becomes a2bc3, and abc does not change. A run is always a maximal block of equal letters: aaaa is a4, not a2a2. You are given a string text and an integer budget. Before compressing, you may delete at most budget characters of text, any you like (the rest keep their order). Return the smallest length of the compressed string you can achieve.

Example 1

text='xxxyzzzzw', budget=2 → 4

Without deletions the code is x3yz4w, length 6. Deleting y and w leaves xxxzzzz, whose code x3z4 has length 4.

Example 2

text='pqppp', budget=1 → 2

Delete q to get pppp, coded as p4.

Example 3

text='bbbbbbbbbbbb', budget=3 → 2

Twelve bs are coded as b12 (length 3). Deleting three of them leaves b9, of length 2.

Constraints

1 ≤ text.length ≤ 120
0 ≤ budget ≤ text.length
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='xxxyzzzzw', budget=2

Expected

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