<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:
        n = len(s)
        @lru_cache(None)
        def dp(index, last_char, last_char_count, k):
            if k < 0:
                return math.inf
            if index == n:
                return 0
            delete_char = dp(index+1, last_char, last_char_count, k-1)
            if s[index] == last_char:
                if last_char_count not in [1, 9, 99]:
                    keep_char = dp(index+1, last_char, last_char_count+1, k)
                else:
                    keep_char = dp(index+1, last_char, last_char_count+1, k)+1
            else:
                keep_char = dp(index+1, s[index], 1, k)+1
            return min(delete_char, keep_char)
        return dp(0, '', 0, k)


        # # not working
        # n = len(s)
        # new_s = ''
        # consecutive_tracking = [1]
        # prev_letter = s[0]
        # count = 1
        # for i in range(1, n):
        #     curr_letter = s[i]
        #     if curr_letter == prev_letter:
        #         count += 1
        #     else:
        #         if count > 1:
        #             new_s += prev_letter+str(count)
        #         else:
        #             new_s += prev_letter
        #         count = 1
        #     prev_letter = curr_letter
        #     consecutive_tracking.append(count)
        # if count > 1:
        #     new_s += prev_letter+str(count)
        # else:
        #     new_s += prev_letter
        # dp = [[0 for _ in range(k+1)] for _ in range(n)]
        # dp[0][0] = 1
        # for i in range(1, n):
        #     if s[i] == s[i-1]:
        #         if consecutive_tracking[i-1] in [1, 9, 99]:
        #             dp[i][0] = dp[i-1][0]+1
        #         else:
        #             dp[i][0] = dp[i-1][0]
        #     else:
        #         dp[i][0] = dp[i-1][0]+1
        # for p in range(n):
        #     for q in range(1, k+1):
        #         if p+1 <= q:
        #             dp[p][q] = 0
        #             continue
        #         if s[p] == s[p-1]:
        #             delete = dp[p-1][q-1]
        #             prev_different_letter_index = p-consecutive_tracking[p]
        #             if prev_different_letter_index < 0:
        #                 dp[p][q] = delete
        #             else:
        #                 keep_whole_block = dp[prev_different_letter_index][q]+len(str(consecutive_tracking[p]))+1
        #                 if consecutive_tracking[p-1] == 1:
        #                     amend_block = dp[p-2][q-1]+1
        #                 elif consecutive_tracking[p-1] == 9:
        #                     choice1 = dp[prev_different_letter_index][q-1]+2
        #                     if q >= 9:
        #                         choice2 = dp[prev_different_letter_index][q-9]+1
        #                     else:
        #                         choice2 = math.inf
        #                     amend_block = min(choice1, choice2)
        #                 elif consecutive_tracking[p-1] == 99:
        #                     choice1 = dp[prev_different_letter_index][q-1]+3
        #                     if q >= 91:
        #                         choice2 = dp[prev_different_letter_index][q-91]+2
        #                     else:
        #                         choice2 = math.inf
        #                     if q >= 99:
        #                         choice3 = dp[prev_different_letter_index][q-99]+1
        #                     else:
        #                         choice3 = math.inf
        #                     amend_block = min(choice1, choice2, choice3)
        #                 else:
        #                     if consecutive_tracking[p-1] <= q:
        #                         amend_block = dp[prev_different_letter_index][q-consecutive_tracking[p-1]]+1
        #                     else:
        #                         amend_block = math.inf
        #                 dp[p][q] = min(delete, keep_whole_block, amend_block)
        #         else:
        #             # this part is wrong, aabbaa if delete bb, then by connecting a, we can save one character
        #             delete = dp[p-1][q-1]
        #             keep = dp[p-1][q]+1
        #             dp[p][q] = min(keep, delete)
        #             deletion_count = 0
        #             prev_block_index = p-1
        #             while deletion_count <= q and prev_block_index >= 0:
        #                 prev_block_index = p-1-consecutive_tracking[prev_block_index]
        #                 if s[prev_block_index] == s[p]:
        #                     curr_deletion = p-1-prev_block_index
        #                     deletion_count += curr_deletion
        #                     dp[p][q] = min(dp[p][q], dp[prev_different_letter_index][q-deletion_count]+++++++++)
        # return dp[-1][-1]

373300