<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:
    # what is the range of values len(s) can take on? [1, 100]
    # what is the range of values k can take on? [0, len(s)]
    # what is the range of values s[i] can take on? only lowercase english letters
    # can s be a null reference? no
    # we are returning a minimized integer!
    # is the answer unique? yes
    # is the answer >= 0? yes

    # idea 0
    # brute force
    # for any combo of <=k characters
    #   delete these <=k characters
    #   record length of compressed string
    #    ^^^ update this length to an ans variable if necessary
    # return smallest, recorded length

    # idea 1
    # dynamic programming for a minimization problem
    # go from left to right and find letters to delete
    #    in a substring of s
    # update the length of the smallest substring

    
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # LeetCode Editorial Approach #1 (memoized bottom up DP)
        n = len(s)
        dp_cache = {}
        def dp(idx,last_char,last_char_count,k):
            if (idx,last_char,last_char_count,k) in dp_cache:
                return dp_cache[(idx,last_char,last_char_count,k)]
            if k < 0:
                # k must be >= 0
                return float("inf")
            if idx == n:
                # reached the end of the 's' string
                return 0
            # let's see what happens if we delete this char
            #    and move on to the next index
            delete_char = dp(idx+1,last_char, last_char_count,k-1)
            if s[idx] == last_char:
                # it seems this char is the same as last char,
                #   so let's keep this char and keep the streak going
                keep_char = (
                    dp(
                        idx+1,
                        last_char,
                        last_char_count+1,
                        k
                    ) +
                    # we'll increase the compressed string length
                    #    by one if last_char_count was in this array
                    (last_char_count in [1,9,99])
                )
            else: # s[idx] != last_char
                # we broke our streak,
                #   let's see what happens if we keep this char
                #   anyways
                keep_char = (
                    dp(
                        idx+1,
                        # reset last_char to this char
                        s[idx],
                        # reset streak here
                        1,
                        k
                    )
                    # we must add one because we found
                    #   a new character that starts off a
                    #   new streak
                    + 1
                )
            # choose the smallest option
            #   between keeping a character
            #   and deleting a character
            res = min(keep_char,delete_char)
            dp_cache[(idx,last_char,last_char_count,k)] = res
            return res
        return dp(0,'',0,k)
        # Time = O(N * N * K) = O(N^2 * K) for populating
        #    <= N * N * K in dp_cache. Note that the total
        #    number of (last_char, last_char_count) pairs
        #    does NOT exceed N.
        #    NOTE: ^^^ The editorial says O(N * K^2), but
        #          I believe the editorial made a typo
        # Memory = O(N * N * K) = O(N^2 * K) for the
        #    max size of the dp_cache hashmap
        #    NOTE: ^^^ The editorial says O(N * K^2), but
        #          I believe the editorial made a typo
        
359300