<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:
        return self._sol4(s, k)

    def _sol4(self, s: str, k: int) -> int:
        def get_length(count: int) -> int:
            if count <= 2:
                return count
            elif count < 10:
                return 2
            elif count < 100:
                return 3
            return 4
            
        @cache
        def helper(s_i: int, k: int) -> int:
            min_length = math.inf
            if k:
                min_length = helper(s_i - 1, k - 1) if s_i else 0
            count = 0
            for i in range(s_i, -1, -1):
                if s[i] == s[s_i]:
                    count += 1
                elif not k:
                    break
                else:
                    k -= 1
                sub_length = helper(i - 1, k) if i else 0
                min_length = min(min_length, sub_length + get_length(count))
            return min_length
        return helper(len(s) - 1, k)
                
            

    # Okay with 1 or 2 simple tweaks I got this to work on 2 of the test cases, but a fundamental flaw is aabbaa, final length should be
    #   from a4 not a2a2.
    # I was working on updating this to fix that but decided to abort the attempt for now, so this isn't expected to work right now
    def _sol3(self, s: str, k: int) -> int:
        run_len_stack = []
        for c in s:
            if run_len_stack and run_len_stack[-1][0] == c:
                run_len_stack[-1][1] += 1
            else:
                run_len_stack.append([c, 1])
        CUTOFFS = [99, 9, 1, 0]
        @cache
        def _get_max_savings(i: int, k: int) -> List:
            if i < 0 or k <= 0:
                return [0, []]
            max_savings, removals = _get_max_savings(i - 1, k)
            _, char_count = run_len_stack[i]
            savings_here = 0
            for cutoff in CUTOFFS:
                if char_count <= cutoff:
                    continue
                savings_here += 1
                if char_count - cutoff <= k:
                    possible_savings, possible_removals = _get_max_savings(i - 1, k - (char_count - cutoff))
                    if possible_savings > max_savings:
                        max_savings = possible_savings
                        removals = possible_removals
                    max_savings = max(max_savings, None) # nocommit
            return max_savings
        # Generate the length of the string, then subtract the max savings
        raw_size = 0
        for _, char_count in run_len_stack:
            for i, cutoff in enumerate(CUTOFFS):
                if char_count > cutoff:
                    raw_size += 4 - i
                    break
        res = raw_size - _get_max_savings(len(run_len_stack) - 1, k)
        return res

    @staticmethod
    def _get_length(count: int) -> int:
        if count <= 2:
            return count
        elif count < 10:
            return 2
        elif count < 100:
            return 3
        return 4

    # Perf: 94.0% 1071 ms, 81.7% 20.5 mb.
    def _sol2(self, s: str, k: int) -> int:
        if k == len(s):
            return 0
        # Note that max_i is inclusive
        @cache
        def dp(max_i: int, cuts_left: int) -> int:
            if max_i < 0:
                return 0
            best = math.inf
            if cuts_left:
                best = dp(max_i - 1, cuts_left - 1)
            count = 0
            for j in range(max_i, -1, -1):
                if s[j] == s[max_i]:
                    count += 1
                elif not cuts_left:
                    return best
                else:
                    cuts_left -= 1
                best = min(best, dp(j - 1, cuts_left) + self._get_length(count))
            return best
        return dp(len(s) - 1, k)

    # Somewhat surprisingly this actually works for 19 / 144 testcases at least, failing on the 20th (in that case because some of
    # the gaps we take away also remove some of the one-to-ones we want to use to wrap up).
    # But ultimately I feel like this just isn't the right approach. By the end of this function I had knowingly given up on a truly
    # correct approach for now and just gone with a heuristic.
    def _sol1(self, s: str, k: int) -> int:
        if k >= len(s):
            return 0
        one_to_one_count = 0
        char_array = []
        running_count = 1
        last_char = s[0]
        for i in range(1, len(s) + 1):
            if i != len(s) and s[i] == last_char:
                running_count += 1
            else:
                char_array.append([last_char, running_count, i - 1])
                if running_count < 3:
                    one_to_one_count += running_count
                elif running_count in [10, 100]:
                    one_to_one_count += 1
                running_count = 1
                if i < len(s):
                    last_char = s[i]
        print(one_to_one_count)
        last_indices = collections.defaultdict(list)
        good_savings = []
        bad_savings = []
        need_to_check_bad = one_to_one_count < k
        running_i = 0
        compressed_str_len = 0
        for char, count, last_i in char_array:
            if last_indices[char]:
                for j in range(len(last_indices[char]) - 1, -1, -1):
                    last_data = last_indices[char][j]
                    distance = running_i - last_data[1]
                    if distance > k:
                        break
                    savings = compressed_str_len - last_data[2] + 1 - len(str(count + last_data[0]))
                    if count > 1:
                        savings += len(str(count))
                    if last_data[0] > 1:
                        savings += len(str(last_data[0]))
                    if savings > distance:
                        print(char, running_i, savings, distance)
                        good_savings.append((savings, distance))
                    elif need_to_check_bad:
                        bad_savings.append((savings, distance))
                    break
            # Damn, it gets particularly complex when we have multiple joinings that could be done, with various costs, a combinatorial
            # explosion even when just talking about ways to join chains of this one character!
            #   Okay, just go without that bit for now and go with what's effectively a heuristic, see if that's enough.
            compressed_str_len += 1
            if count > 1:
                compressed_str_len += len(str(count))
            last_indices[char].append([count, last_i, compressed_str_len])
            running_i = last_i
        # Now we have to do full backtracking for all savings
        max_savings = 0
        max_s_cost = 0
        def helper(running_savings: int, running_costs: int, i: int) -> None:
            if i == len(good_savings):
                return
            nonlocal max_savings, max_s_cost
            new_cost = running_costs + good_savings[i][1]
            if new_cost <= k:
                new_savings = running_savings + good_savings[i][0]
                if new_savings > max_savings:
                    max_savings = new_savings
                    max_s_cost = new_cost
                if new_cost == k:
                    return
                helper(new_savings, new_cost, i + 1)
            helper(running_savings, running_costs, i + 1)
        helper(0, 0, 0)
        print(max_savings, max_s_cost)
        compressed_str_len -= max_savings
        new_k = k - max_s_cost
        one_to_one_used = min(new_k, one_to_one_count)
        compressed_str_len -= one_to_one_used
        return compressed_str_len


    # I caught this before even testing running, I'm glad of. I mistakenly thought k was the number of chains we compress.
    def _wrong(self, s: str, k: int) -> int:
        new_length = len(s)
        savings = []
        running_count = 1
        last_char = s[0]
        for i in range(1, len(s)):
            if s[i] == last_char:
                running_count += 1
            else:
                last_char = s[i]
                if running_count > 2:
                    savings.append(running_count - 2)
                running_count = 1
        if running_count > 2:
            savings.append(running_count - 2)
        savings.sort(reverse=True)
        for i in range(min(k, len(savings))):
            new_length -= savings[i]
        return new_length
        
20500