525. Shortest Encoding After Deletions

A string is run-length encoded by replacing each run of equal characters with the character followed by its count, and a run of length 1 gets no number:

aabccc -> a2bc3 length 5 a -> a length 1 aaaaaaaaaaa -> a11 length 3

Delete at most k characters, in any positions. Print the shortest possible encoded length.

aaabcccd, k = 2 -> 4 delete b and d, leaving aaaccc -> a3c3 aabbaa, k = 2 -> 2 delete the two b, leaving aaaa -> a4

## Why the obvious state is not enough

(position, deletions used) looks like the state, and it is not, because the encoded length of a run depends on the run's TOTAL length, which is only known once the run ends. A decision at position i cannot be costed without knowing how far the current run extends.

The fix is to make the run a unit of the recursion rather than a property carried through it.

## The recurrence

go(i, rem) = the shortest encoding of s[i..] using at most rem deletions

At position i there are two kinds of move:

delete s[i] go(i+1, rem-1) keep a RUN of s[i] scan forward from i, keeping every s[i] and deleting every other character, and charge the run's encoded cost

The second is the part that matters. Rather than deciding one character at a time, it commits to a whole run: for each j >= i, keep all the characters equal to s[i] in s[i..j], delete the rest, and pay 1 + digits(count) plus go(j+1, rem - deleted).

Making the RUN the unit is what lets the cost be charged correctly, and it is the general move whenever a cost is a function of a group rather than of an element.

## The digit count

A run of length 1 costs 1, of length 2 to 9 costs 2, of 10 to 99 costs 3, and of 100 to 999 costs 4. Writing the cost as 1 + len(str(count)) unconditionally charges 2 for a single character and is wrong on any input with an isolated character.

abc with k = 3 answers 0, and abc with k = 0 would answer 3, one per character. A solution charging 2 each answers 6.

## The early exit

If rem >= n - i then everything remaining can be deleted, so the answer is 0. Without that check the recursion still terminates, but it explores states that cannot improve anything.

## Boundaries

a with k = 0 answers 1 and with k = 1 answers 0. Deleting everything is allowed and the empty string encodes to length 0.

aaaaaaaaaaa with k = 0 answers 3, which is a11, and is the test for the multi-digit count.

aabbcc with k = 0 answers 6, three runs of two, each costing 2.

aaabbb with k = 3 answers 2: delete one whole group and keep a3 or b3. Not 4, which is what deleting three characters spread across both groups gives.

## Cost

Time O(n^2 k). Space O(n k) for the memo.

Constraints - `1 ≤ length of s ≤ 100` - `0 ≤ k ≤ length of s` - `s` contains only lowercase letters