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.