<p><a href="http://en.wikipedia.org/wiki/Run-length_encoding">Run-length encoding</a> is a string compression method that works by&nbsp;replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string&nbsp;<code>&quot;aabccc&quot;</code>&nbsp;we replace <font face="monospace"><code>&quot;aa&quot;</code></font>&nbsp;by&nbsp;<font face="monospace"><code>&quot;a2&quot;</code></font>&nbsp;and replace <font face="monospace"><code>&quot;ccc&quot;</code></font>&nbsp;by&nbsp;<font face="monospace"><code>&quot;c3&quot;</code></font>. Thus the compressed string becomes <font face="monospace"><code>&quot;a2bc3&quot;</code>.</font></p>

<p>Notice that in this problem, we are not adding&nbsp;<code>&#39;1&#39;</code>&nbsp;after single characters.</p>

<p>Given a&nbsp;string <code>s</code>&nbsp;and an integer <code>k</code>. You need to delete <strong>at most</strong>&nbsp;<code>k</code> characters from&nbsp;<code>s</code>&nbsp;such that the run-length encoded version of <code>s</code>&nbsp;has minimum length.</p>

<p>Find the <em>minimum length of the run-length encoded&nbsp;version of </em><code>s</code><em> after deleting at most </em><code>k</code><em> characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaabcccd&quot;, k = 2
<strong>Output:</strong> 4
<b>Explanation: </b>Compressing s without deleting anything will give us &quot;a3bc3d&quot; of length 6. Deleting any of the characters &#39;a&#39; or &#39;c&#39; would at most decrease the length of the compressed string to 5, for instance delete 2 &#39;a&#39; then we will have s = &quot;abcccd&quot; which compressed is abc3d. Therefore, the optimal way is to delete &#39;b&#39; and &#39;d&#39;, then the compressed version of s will be &quot;a3c3&quot; of length 4.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aabbaa&quot;, k = 2
<strong>Output:</strong> 2
<b>Explanation: </b>If we delete both &#39;b&#39; characters, the resulting compressed string would be &quot;a4&quot; of length 2.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaaaaaaaaaa&quot;, k = 0
<strong>Output:</strong> 3
<strong>Explanation: </strong>Since k is zero, we cannot delete anything. The compressed string is &quot;a11&quot; of length 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>0 &lt;= k &lt;= s.length</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        
        # we borrow some code from #443:

        groups = []
        number = 1

        for readI, C in enumerate(s):
            atEndOfList = ((readI + 1) >= len(s))
            nextC = ('-' if atEndOfList else s[readI + 1])
            nextCDifferent = (C != nextC)
            if nextCDifferent:
                print(f'{readI=} "{nextC}" "{C}" x {number}')
                toWrite = [C]
                if number > 1:
                    toWrite += list(str(number))
                groups.append(
                    (C, number, len(toWrite))
                )
                number = 1
            else:
                number += 1

        print(f'{groups=}')
        length_without_deletions = sum(
            length
            for (char, count, length) in groups
        )
        print(f'{length_without_deletions=}')

        @cache
        def useful_numbers_to_delete(N: int) -> Set[int]:
            # print(f'UNTD({N}):')
            answers = {0, N}    # delete everything, delete nothing
            if N > 1:
                answers.add(N-1)    # delete all but one: len("a") < len("a2")
            # print(f'  {answers=}')
            length = len(str(N))
            for new_len in range(1, length):
                new_num = int('9' * new_len)
                diff = N - new_num
                # print(f'    +{new_len=} {new_num=} {diff=}')
                answers.add(diff)
            return answers
        
        @cache
        def useful_numbers_under_K(N: int, K: int) -> Set[int]:
            # print(f'UNUK({N},{K}):')
            return {
                num
                for num in useful_numbers_to_delete(N)
                if num <= K
            }
        
        possibles = {
            # we start with only one possibility:
            (
                0,      # length so far
                k,      # K characters left to delete
                '-',    # last character used: something impossible
                0,      # count of last character
                0,      # length of last group
            )
        }

        for G in groups:
            print(f'{G=}')
            (char, immutable_count, length) = G
            new_possibles = set()
            for P in possibles:
                count = immutable_count
                # print(f'  {P=}')
                (
                    length_so_far,
                    remaining_k,
                    prior_char,
                    prior_count,
                    prior_length, 
                ) = P
                allow_delete_all = True
                if char == prior_char:
                    # print(f'    Merge prior group into this one')
                    length_so_far -= prior_length
                    count += prior_count
                    allow_delete_all = False
                    # print(f'    ({length_so_far=})')
                    # print(f'    ({count=})')
                delete_options = useful_numbers_under_K(count, remaining_k)
                # print(f'    {delete_options=}')
                for D in delete_options:
                    trial_count = count - D
                    # print(f'    {D=} {trial_count=}')
                    
                    if trial_count == 0:
                        if not allow_delete_all:
                            # print(f'      Cannot delete all {count} "{char}"')
                            pass
                        
                        else:
                            # print(f'      Deleted all {count} "{char}"')
                            Q = (
                                length_so_far,
                                remaining_k - D,
                                prior_char,
                                prior_count,
                                prior_length,
                            )
                            # print(f'      {Q=}')
                            new_possibles.add(Q)
                        continue

                    trial_length = 1 + (
                        0
                        if trial_count == 1
                        else len(str(trial_count))
                    )
                    Q = (
                        length_so_far + trial_length,
                        remaining_k - D,
                        char,
                        trial_count,
                        trial_length,
                    )
                    # print(f'      {Q=}')
                    new_possibles.add(Q)
            possibles = new_possibles

        print(f'DONE')
        print(f'{possibles=}')

        return min([
            length
            for (length, remaining_k, prior_char, prior_count, prior_length) in possibles
        ])

29600