Run-length encoding is a string compression method that works by 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 "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". Thus the compressed string becomes "a2bc3".
Notice that in this problem, we are not adding '1' after single characters.
Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length.
Find the minimum length of the run-length encoded version of s after deleting at most k characters.
 
Example 1:
Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.
Example 2:
Input: s = "aabbaa", k = 2
Output: 2
Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.

Example 3:
Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.

 
Constraints:

1 <= s.length <= 100
0 <= k <= s.length
s contains only lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        

Solutions:
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)

        def compLen(c):
            return 1 + len(str(c)) if c > 1 else 1

        @lru_cache(None)
        def dp(i, k): # return {head: (len, -head_count)}
            if (n - i) <= k:
                return {} # remove all
            x, res = s[i], {}
            # remove
            if k:
                res = dp(i + 1, k - 1)
            # keep
            keep = dp(i + 1, k)
            t = [(1 + min((leng for leng, _ in list(keep.values())), default=0), -1)]
            if x in keep:
                leng, negc = keep[x]
                leng, negc = (leng - compLen(-negc) + compLen(-negc + 1),
                              negc - 1)
                t.append((leng, negc))
            if x in res:
                t.append(res[x])
            res[x] = min(t)
            return res

        m = dp(0, k)
        return min((leng for leng, _ in list(m.values())), default = 0)


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        def _len(cnt): return 1 if cnt == 1 else 2 if cnt <= 9 else 3 if cnt <= 99 else 4

        @lru_cache(None)
        def solve(left, k):
            if k < 0:
                return float('inf')
            # remove s[0:left+1]
            if left + 1 == k:
                return 0
            # 1. keep s[left]
            # 2. remove s[left]
            res = min(solve(left - 1, k) + 1, solve(left - 1, k - 1))
            cnt = 1
            for j in range(left - 1, -1, -1):
                if s[j] != s[left]:
                    k -= 1
                    if k < 0:
                        break
                else:
                    cnt += 1
                    if j < k:
                        break
                    res = min(res, solve(j - 1, k) + _len(cnt)) 
            return res
        return solve(len(s) - 1, k)


from typing import *
from functools import lru_cache



class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:

        def get_compressed_len(n):
            if n == 0:
                return 0
            if n == 1:
                return 1
            return len(str(n)) + 1

        @lru_cache(None)
        def dp_memo(x, y, left_count, remain_k):
            if x > y:
                return 0

            # 1. don't concat s[x] with any further character
            ans = get_compressed_len(left_count + 1) + dp_memo(x + 1, y, 0, remain_k)

            # 2. remove s[x]
            if remain_k > 0:
                ans = min(ans, get_compressed_len(left_count) + dp_memo(x + 1, y, 0, remain_k - 1))

            # 3. try to concat s[x] with further character s[xx]
            for i in range(remain_k + 1):
                xx = x + i + 1
                if xx > y:  # out of bounds
                    break
                if s[x] == s[xx]:  # same s[x] and s[xx], concat them
                    ans = min(ans, dp_memo(xx, y, left_count + 1, remain_k - i))

            # print(x, y, left_count, remain_k, '->', ans)
            return ans
        return dp_memo(0, len(s) - 1, 0, k)

class Solution:    
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[n if i > 0 else 0] * (k + 1) for i in range(n + 1)]
        
        def cost(v):
            return (1 + len(str(v))) if v > 1 else v
        
        for i in range(n):
            for j in range(k + 1):
                if j:
                    dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j])
                take = 0
                for x in range(i + 1)[::-1]:
                    if s[x] != s[i]:
                        take += 1
                    if take > j:
                        break
                    dp[i + 1][j - take] = min(dp[i + 1][j - take], dp[x][j] + cost(i - x - take + 1))        
        return min(dp[n])

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        states = { # (deletions, last character, multiple) -> minimum length
            (0, None, 0): 0
        } 
        
        def count_len(d):
            if d == 0 or d == 1:
                return 0
            else:
                return len(str(d))
        
        for c in s:
            new_states = collections.defaultdict(lambda: float('inf'))
            for (deletions, last_char, count), length in states.items():
                # with deletion
                if deletions < k:
                    new_state = (deletions + 1, last_char, count)
                    new_length = length
                    new_states[new_state] = min(new_states[new_state], new_length)
                # without deletion
                if c == last_char:
                    new_state = (deletions, c, count + 1)
                    new_length = length - count_len(count) + count_len(count + 1)
                else:
                    new_state = (deletions, c, 1)
                    new_length = length + 1
                new_states[new_state] = min(new_states[new_state], new_length)
            states = new_states
            
        min_length = float('inf')
        for (deletions, last_char, count), length in states.items():
            if deletions == k:
                min_length = min(min_length, length)
        return min_length

class Solution:
    def getLengthOfOptimalCompression(self, s: str, K: int) -> int:
        def getCost(k):
            if k <= 1:
                return k
            else:
                return 1 + len(str(k))
        
        n = len(s)
        dp = [[n] * (K + 1) for i in range(n+1)]
        dp[0] = [0] * (K + 1)
        for i in range(n):
            for j in range(K+1):
                if j > 0:
                    dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j]) # delete at position i
                take = 0
                for k in range(i+1)[::-1]: # keep at position i, iterate length of suffix you keep
                    if s[k] != s[i]:
                        take += 1
                    if take > j:
                        break
                    dp[i+1][j-take] = min(dp[i+1][j-take], dp[k][j] + getCost(i - k - take + 1))
                    
        return min(dp[n])

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        '''
        DP

        dp(i, k) := minimal length for encoded string starting from 'i' with 'k' characters removed
        dp(i, k) = min(dp(i, k-1), dp(j, k))
        '''

        def segment2Len(segment):
            if segment[1] <= 1: return segment[1]
            return len(str(segment[1])) + 1

        segments = []
        start = 0
        for i in range(1, len(s)):
            if s[i] != s[i-1]:
                segments.append([s[i-1], i-start, start])
                start = i
        segments.append([s[-1], len(s)-start, start])
        
        def minLength(pChar, pLen, i, k, mem):
            key = (pChar, pLen, i, k)
            if key in mem: return mem[key]

            if k == 0:
                mem[key] = sum(map(segment2Len, segments[i:])) + segment2Len([pChar, pLen])
                return mem[key]

            if i == len(segments):
                mem[key] = segment2Len([pChar, max(0, pLen-k)])
                return mem[key]
            
            lengths = []
            curLen = pLen + 2
            for j in range(min(pLen, k) + 1):
                newLen = segment2Len([pChar, pLen - j])
                if newLen < curLen:
                    lengths.append(newLen + minLength(segments[i][0], segments[i][1], i+1, k-j, mem))
                    curLen = newLen

            for j in range(i, len(segments)):
                subStrLen = segments[j][2] - segments[i][2]
                if subStrLen <= k:
                    if segments[j][0] == pChar:
                        lengths.append(minLength(pChar, pLen+segments[j][1], j+1, k-subStrLen, mem))
                else:
                    break

            mem[key] = min(lengths)
            return mem[key]

        mem = {}
        ans = minLength('', 0, 0, k, mem)
        return ans


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        
        def get_code_len(x):
            if x == 1: return 1
            return len(str(x)) + 1 if x >= 2 else 0
        
        n = len(s)
        dp = [ [n] * (k + 1) for _ in range(len(s) + 1)]
        dp[0] = [ 0 ] * (k + 1)
        for i in range(n):
            for j in range( k + 1):
                if j > 0:
                    dp[i + 1][j - 1] = min(dp[i][j], dp[i + 1][j - 1])
                
                deleted = 0
                for p in reversed(list(range(i + 1))):
                    # delete different 
                    if s[i] != s[p]:
                        deleted += 1
                    if deleted > j:
                        break
                    dp[i + 1][j - deleted] = min(
                        dp[i + 1][j - deleted], 
                        dp[p][j] + get_code_len( i + 1 - p - deleted))
        return min(dp[n])


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def get(index, left, c, streak):
            if left < 0: return 1e6
            if index == len(s):
                return ((1 + len(str(streak))) - (streak == 1)) * (streak > 0)
            return min(
                ((1 + len(str(streak))) - (streak == 1)) * (streak > 0) * (c != s[index]) + get(index+1, left, s[index], 1 + streak * (c == s[index])),
                get(index+1, left-1, c, streak))
        
        return get(0, k, None, 0)
        


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        memo={}
        def counter(start, last, last_count, left):
            if (start, last, last_count, left) in memo:
                return memo[(start, last, last_count, left)]
            if left<0:
                return sys.maxsize
            if start>=len(s):
                return 0
            
            if s[start]==last:
                incre=1 if last_count==1 or last_count==9 or last_count==99 else 0
                memo[start, last, last_count, left]=incre+counter(start+1, last, last_count+1, left)
            else:
                keep=1+counter(start+1, s[start], 1, left)
                delete=counter(start+1, last, last_count, left-1)
                memo[start, last, last_count, left]=min(keep, delete)
            return memo[start, last, last_count, left]
        return counter(0, '', 0, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def get(index, left, c, streak):
            val = ((1 + len(str(streak))) - (streak == 1)) * (streak > 0)
            if left < 0 or index == len(s): return 1e6 if left < 0 else val
            return min(val*(c!=s[index])+get(index+1,left,s[index],1+streak*(c==s[index])),get(index+1,left-1,c,streak))
        return get(0, k, None, 0)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def get(index, left, c, streak):
            val = ((1 + len(str(streak))) - (streak == 1)) * (streak > 0)
            if left < 0 or index == len(s): return 1e6 if left < 0 else val
            return min(val*(c != s[index]) + get(index+1, left, s[index], 1 + streak * (c == s[index])),get(index+1, left-1, c, streak))
        return get(0, k, None, 0)
        


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:    
        
        def get_code_len(x):
            return 1 + len(str(x)) if x > 1 else x
        
        n = len(s)
        dp = [[ n ] * (k + 1) for i in range(n + 1)]
        dp[0] = [0] * (k + 1)
        for i in range(n):
            for j in range(k + 1):
                if j > 0:
                    dp[i + 1][j - 1] = min(dp[i+1][j-1], dp[i][j])
                    
                deletions = 0
                for p in reversed(range(i+1)): 
                    if s[p] != s[i]:
                        deletions += 1
                    if deletions > j:
                        break
                    dp[i+1][j - deletions] = min(dp[i + 1][j - deletions],
                                          dp[p][j] + get_code_len(i - p - deletions + 1))
                    
        return min(dp[n])

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        dp = {}
        def dfs(i, t, prev, last):
            if t == -1:
                return float('inf')
            if i == len(s):
                return 0
            if (i, t, prev, last) in dp:
                return dp[(i, t, prev, last)]
            if s[i] == last:
                increase = 0
                if prev == 1 or prev == 9 or prev == 99:
                    increase = 1
                dp[(i, t, prev, last)] = increase + dfs(i + 1, t, prev + 1, last)
            else:
                take = dfs(i + 1, t, 1, s[i]) + 1
                remove = dfs(i + 1, t - 1, prev, last)
                dp[(i, t, prev, last)] = min(take, remove)
            return dp[(i, t, prev, last)]
        return dfs(0, k, 0, '')


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        memo = {}
        def f(i, run_ch, run_length, remain_dels):
            if i == len(s):
                return 0
            key = (i, run_ch, run_length, remain_dels)
            if key in memo:
                return memo[key]
            
            del_costs = float('inf')
            if remain_dels > 0:
                del_costs = f(i+1, run_ch, run_length, remain_dels-1)
            keep_costs = 0
            if s[i] == run_ch:
                extra_cost = 0
                if run_length == 1 or len(str(run_length+1)) > len(str(run_length)):
                    extra_cost = 1
                keep_costs = extra_cost + f(i+1, run_ch, run_length+1, remain_dels)
            else:
                keep_costs = 1 + f(i+1, s[i], 1, remain_dels)
            memo[key] = min(keep_costs, del_costs)
            return memo[key]
        return f(0, '', 0, k)

from functools import lru_cache

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        c = []
        idx = 0
        tmp = 0
        while idx < len(s):
            if idx >= 1 and s[idx] != s[idx - 1]:
                c.append((s[idx - 1], tmp))
                tmp = 1
            else:
                tmp += 1
            if idx == len(s) - 1 and (len(c) == 0 or c[-1][0] != s[idx]):
                c.append((s[idx], tmp))
            idx += 1
        def rl(x):
            if x[1] == 1:
                return 1
            if 2 <= x[1] < 10:
                return 2
            if x[1] == 100:
                return 4
            return 3
        if len(s) >= 100 and len(c) == 1:
            return rl((c[0]))
        @lru_cache(None)
        def dfs(i, r, prev=None, d=False):
            if i == len(c):
                return 0
            out = dfs(i + 1, r, c[i]) + rl(c[i])
            if r >= c[i][1] and not d:
                if i + 1 < len(c) and prev and prev[0] == c[i + 1][0]:
                    c[i + 1] = (c[i + 1][0], c[i + 1][1] + prev[1])
                    out = min(out, dfs(i + 1, r - c[i][1], prev, True) - rl(prev))
                    c[i + 1] = (c[i + 1][0], c[i + 1][1] - prev[1])
                else:
                    out = min(out, dfs(i + 1, r - c[i][1], prev))
            if c[i][1] >= 10 and r - c[i][1] + 9 >= 0:
                out = min(out, dfs(i + 1, r - c[i][1] + 9, (c[i][0], 9)) + 2)
            if c[i][1] >= 2 and r - c[i][1] + 1 >= 0:
                out = min(out, dfs(i + 1, r - c[i][1] + 1, (c[i][0], 1)) + 1)
            return out
        
        return dfs(0, k)

            


class Solution:
    def getLengthOfOptimalCompression(self, s, k):
        n = len(s)
        dp = [[9999] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0

        for i in range(1, n + 1):
            for j in range(k + 1):
                cnt = 0
                del_ = 0
                for l in range(i, 0, -1): # Keep s[i - 1], remove s[l - 1] if it's different char
                    if s[l - 1] == s[i - 1]:
                        cnt += 1
                    else:
                        del_ += 1
                    if j - del_ >= 0:
                        dp[i][j] = min(dp[i][j], dp[l - 1][j - del_] + 1 + (3 if cnt > 99 else 2 if cnt > 9 else 1 if cnt > 1 else 0))
                if j > 0: # remove s[i - 1]
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1])

        return dp[n][k]

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        memo = {}
        def f(i, run_ch, run_len, remain_dels):
            if i == len(s):
                return 0
            key = (i, run_ch, run_len, remain_dels)
            if key in memo:
                return memo[key]
            del_costs = float('inf')
            if remain_dels > 0:
                del_costs = f(i+1, run_ch, run_len, remain_dels-1)
            
            keep_costs = 0
            if s[i] == run_ch:
                extra_cost = 0
                if run_len == 1 or len(str(run_len+1)) > len(str(run_len)):
                    extra_cost = 1
                keep_costs = extra_cost + f(i+1, run_ch, run_len+1, remain_dels)
            else:
                keep_costs = 1 + f(i+1, s[i], 1, remain_dels)
            
            memo[key] = min(del_costs, keep_costs)
            return memo[key]
        return f(0, '', 0, k)


def stringcomp(a, i, last,k,count, memo):
    if (i, last,k,count) in memo:
        return memo[((i, last,k,count))]
    if k<0:
        return float('inf')
    if i>=len(a):
        return 0
    if a[i] == last:
        keepi = stringcomp(a, i+1, last, k, count+1, memo) + (1 if count in (1, 9,99,999) else 0)
        deletei = stringcomp(a, i+1, last, k-1, count, memo)
    else:
        keepi = 1+stringcomp(a, i+1, a[i], k, 1, memo)
        deletei = stringcomp(a, i+1, last, k-1, count, memo)
    memo[((i, last,k,count))] = min(keepi, deletei)
    return min(keepi, deletei)
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        return stringcomp(s,0,'', k, 0,{})

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        m = {}
        def f(i, cur, length, dels):
            if i == len(s):
                return 0
            key = (i, cur, length, dels)
            if key in m: return m[key]
            del_cost = float('inf')
            if dels>0:
                del_cost = f(i+1, cur, length, dels-1)
            keep = 0
            if s[i]==cur:
                extra = 0
                if length==1 or len(str(length+1))>len(str(length)):
                    extra=1
                keep = extra + f(i+1, cur, length+1, dels)
            else:
                keep =1+f(i+1, s[i], 1, dels)
            m[key]=min(keep, del_cost)
            return m[key]
        return f(0, '', 0, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def get_length(beg: int, last_char: str, n_repeat: str, quota: int) -> int:
            if quota < 0:
                return float('inf')
            if beg == len(s):
                return 0
            if s[beg] == last_char:
                incr = 1 if n_repeat in [1, 9, 99] else 0
                return incr + get_length(beg+1, last_char, n_repeat+1, quota)
            else:
                return min(
                    get_length(beg+1, last_char, n_repeat, quota - 1), # delete this char
                    1 + get_length(beg+1, s[beg], 1, quota)
                )
        return get_length(0, '', 0, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        count = 1
        prev = s[0]
        counts = []
        for l in s[1:]:
            if l == prev:
                count += 1
            else:
                counts.append([prev, count])
                count = 1
                prev = l
        counts.append([prev, count])
        
        @lru_cache(None)
        def opt(i, k):
            if i >= len(counts):
                return 0
            l, c = counts[i]
            best = 1 + (len(str(c)) if c > 1 else 0) + opt(i + 1, k)
            if k >= c:
                best = min(best, opt(i + 1, k - c))
            if c > 1 and c - 1 <= k:
                best = min(best, 1 + opt(i + 1, k - (c - 1)))
            if c > 9 and c - 9 <= k:
                best = min(best, 2 + opt(i + 1, k - (c - 9)))
            if c > 99 and c - 99 <= k:
                best = min(best, 3 + opt(i + 1, k - (c - 99)))
            j = i + 1
            while j < len(counts) and k >= 0:
                if counts[j][0] == l:
                    c += counts[j][1]
                    best = min(best, 1 + (len(str(c)) if c > 1 else 0) + opt(j + 1, k))
                    if k >= c:
                        best = min(best, opt(j + 1, k - c))
                    if c > 1 and c - 1 <= k:
                        best = min(best, 1 + opt(j + 1, k - (c - 1)))
                    if c > 9 and c - 9 <= k:
                        best = min(best, 2 + opt(j + 1, k - (c - 9)))
                    if c > 99 and c - 99 <= k:
                        best = min(best, 3 + opt(j + 1, k - (c - 99)))
                else:
                    k -= counts[j][1]
                j += 1
            return best
        return opt(0, k)
                
            


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        cache = {}
        
        def process(i, x, c, k):
            if not (i, x, c, k) in cache:
                ans = 101
                if i == -1:
                    return 0
                else:
                    # delete s[i]
                    if k > 0:
                        ans = min(ans, process(i-1, x, c, k-1))
                    # keep s[i]
                    if s[i] != x:
                        ans = min(ans, 1+process(i-1, s[i], 1, k))
                    elif c == 1 or c == 9 or c == 99:
                        ans = min(ans, 1+process(i-1, x, c+1, k))
                    else:
                        ans = min(ans, process(i-1, x, c+1, k))            
                
                cache[(i, x, c, k)] = ans
            return cache[(i, x, c, k)]
        
        n = len(s)
        return process(n-1, '*', 0, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def fuck(start,last,c,left):
            if start >= len(s):
                return 0
            if left == 0:
                return (1 if c==99 or c == 9 or c ==1 else 0) +  fuck(start+1, last, c +1, left) if s[start]==last else 1 + fuck(start+1, s[start], 1, left)

            
            return (1 if c==99 or c == 9 or c ==1 else 0) +  fuck(start+1, last, c +1, left) if s[start]==last else min(fuck(start+1, last, c, left-1),1 + fuck(start+1, s[start], 1, left))
        return fuck(0,'sb',0, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        mem={}
        last=[]
        for c in s:
            if not last or c!=last[-1][0]:
                last.append([c,0])
            last[-1][1]+=1
        if len(last)==1:
            if k==len(s):
                return 0
            return len(''.join([x+(str(y-k) if y-k>=2 else '') for x,y in last]))
        ns=''.join([x+(str(y) if y>=2 else '') for x,y in last])
        print(ns)
        def inner(i,lb,ll,ck):
            if ck<0:
                return len(ns)
            if i==len(s):
                return 0
            if (i,lb,ll,ck) not in mem:
                mem[(i,lb,ll,ck)]=inner(i+1,lb,ll,ck-1)
                if s[i]==lb:
                    nll=ll+1
                    if nll==2 or nll==10:
                        mem[(i,lb,ll,ck)]=min(mem[(i,lb,ll,ck)], inner(i+1,lb,nll,ck)+1)
                    else:
                        mem[(i,lb,ll,ck)]=min(mem[(i,lb,ll,ck)], inner(i+1,lb,nll,ck))
                else:
                    mem[(i,lb,ll,ck)]=min(mem[(i,lb,ll,ck)],1+inner(i+1,s[i],1,ck))
            return mem[(i,lb,ll,ck)]
        print(mem)
        return inner(0,None,0,k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        self.memo = {}
        return self.helper(0, 0, '', s, k)
    
    def helper(self, i, last_count, last_ch, s, k):
        if i == len(s):
            length_count = len(str(last_count)) if last_count > 1 else 0
            length_ch = len(last_ch)
            return length_count + length_ch
        
        if (i, last_count, last_ch, k) in self.memo:
            return self.memo[(i, last_count, last_ch, k)]
        
        delete = float('inf')
        if k>0:
            delete = self.helper(i+1, last_count, last_ch, s, k-1)
        
        if s[i] == last_ch:
            no_delete = self.helper(i+1, last_count+1, last_ch, s, k)
        else:
            length_count = len(str(last_count)) if last_count > 1 else 0
            length_ch = len(last_ch)
            no_delete = length_count + length_ch + self.helper(i+1, 1, s[i], s, k)
        
        res = min(delete, no_delete)
        self.memo[(i, last_count, last_ch, k)] = res
        return res
    
    

        
        
    
    


class Solution:
    def getLengthOfOptimalCompression(self, s, k):
        memo = {}
        
        def counter(start, last_char, last_char_len, rem_chars):
            nonlocal memo, s
            if rem_chars < 0:
                return float('inf')
            if start == len(s):
                return 0
            if (start, last_char, last_char_len, rem_chars) not in memo:
                if s[start] == last_char:
                    inc = 1 if last_char_len in (1, 9, 99) else 0
                    memo[(start, last_char, last_char_len, rem_chars)] = inc + counter(start + 1, last_char, last_char_len + 1, rem_chars)
                else:
                    # keep
                    keep_len = 1 + counter(start + 1, s[start], 1, rem_chars)
                    # Remove
                    rem_len = counter(start + 1, last_char, last_char_len, rem_chars - 1)
                    memo[(start, last_char, last_char_len, rem_chars)] = min(keep_len, rem_len) 
            return memo[(start, last_char, last_char_len, rem_chars)]

        return counter(0, '', 0, k)

from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
 
        @lru_cache(None)
        def singlelen(n: int) :
            if not isinstance(n, int):
                print(n)
            if n <= 1:
                return n
            elif n < 10:
                return 2
            elif n < 100:
                return 3
            else:
                return 4
            
        def encode(s):
            last, len = '' , 0
            res = []
            for c in s:
                if c == last:
                    len += 1
                else :
                    if last != '':
                        res.append((last, len))
                    last, len = c, 1
            if len != 0:
                res.append((last, len))
            return res
        def add(curchar, curlen: int , code):
            #print(32, type(curlen), end= ' ')
            if len(code) == 0:
                return 0, curchar, curlen 
            
            prevsum  = 0
            for n, l in code:
                if n == curchar:
                    curlen += l
                else:
                    prevsum += singlelen(curlen)
                    curchar, curlen = n, l  
                    #print(43, type(curlen), end= ' ')
            return (prevsum, curchar, curlen) 
        
        @lru_cache(None)
        def dp(code, remain, todel, curchar, curlen: int):
            #print(sum(tuple(zip(*code))[1]), remain, todel, curchar, curlen)
            if remain == todel:
                #print(49, type(curlen), end= ' ')
                return singlelen(curlen)
            if todel == 0:
                (prelen, curchar, curlen) = add(curchar, curlen, code)
                #print(53, type(curlen), end= ' ')
                return prelen + singlelen(curlen)
            
            if len(code) < 1 or len(code[0]) < 1: 
                print((57, code, remain, todel, curchar, curlen))
            if code[0][0] == curchar:
                curlen += code[0][1]
                remain -= code[0][1]
                if remain < todel:
                    curlen += todel - remain
                    remain = todel
                    return singlelen(curlen)
                else:
                    code = code[1:]
                if len(code) == 0:
                    return singlelen(curlen)
                
            cases = []
            
            if todel >= code[0][1]:
                #print(63, type(curlen), end= ' ')
                cases.append(dp(code[1:], remain - code[0][1], todel - code[0][1], curchar, curlen))
        
            (prelen, newchar, newlen) = add(curchar, curlen, code[:1]) 
            #print(67, type(newlen), end= ' ') 
            for trydel in range(max(0, todel - remain + code[0][1] ),  min(code[0][1], todel + 1)) :
                cases.append(prelen  + dp(code[1:], remain - code[0][1], todel - trydel, newchar, newlen - trydel))

            # remove all current stride, remove partial of current stride, keep current stride 
        
            if len(cases) == 0:
                #81       4                          1       1      b        3       -  0       b        5
                #  (('b', 2), ('a', 1), ('c', 1)) ((0, 2), (2, 2))
                #81       2                          1       1      c        4       -  0       c        6 
                # | (('c', 2),)  ((0, 2), (2, 2))
                print((81, sum(tuple(zip(*code))[1]), remain, todel, curchar, curlen,'-',prelen, newchar, newlen, '|', code, ((0, todel - remain + code[0][1] ),  (code[0][1], todel + 1))))
            return min(cases)
        
    
        code = tuple( encode(s))
        print((code, len(s))) 
        print((sum(tuple(zip(*code))[1])))
        
        return dp( code, len(s), k, '', 0)
    
    def getLengthOfOptimalCompression2(self, s: str, k: int) -> int:
        N = len(s)
        if N == k:
            return 0
        @lru_cache(None)
        def singlelen(n) :
            if n <= 1:
                return n
            elif n < 10:
                return 2
            elif n < 100:
                return 3
            else:
                return 4
                
        def finallen(prev):
            return prev[0] + singlelen(prev[1]) 
        
        def add(prev, s):
            if len(s) == 0:
                return prev 
            
            prevsum, curlen, cur = prev
            for n in s:
                if n == cur:
                    curlen += 1
                else:
                    prevsum += singlelen(curlen)
                    curlen, cur= 1, n  
                
            return (prevsum, curlen, s[-1:]) 
        
        @lru_cache(None)
        def dp(s, k, prev):
            if k == 0:
                return finallen(add(prev, s))
            if len(s) == k:
                return finallen(prev)

            cur, s = s[:1], s[1:]
            while cur == prev[2] and len(s) > k:
                prev = add(prev,cur) 
                cur, s = s[:1], s[1:] 

            return min (dp(s, k - 1, prev), dp(s, k, add(prev,cur))) 
        
        return dp(s, k, (0, 0, ''))


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # dp[i][k]: the min length for s[:i+1] with at most k deletion
        # each s[i]: keep or discard
        # if delete: dp[i][j] = dp[i-1][j-1]
        # if keep: delete at most j chars in s[:i+1] that are different from s[i]
        n = len(s)
        dp =[[float('inf') for _ in range(n+1)] for _ in range(n+1)]
        
        dp[0][0] = 0
        for i in range(1, n+1):
            for j in range(k+1):
                cnt = 0
                d = 0
                for l in range(i, 0, -1):
                    if s[l-1] == s[i-1]:
                        cnt += 1
                    else:
                        d += 1
                    if j - d >= 0:
                        diff = 0
                        if cnt >= 100:
                            diff = 3
                        elif cnt >=10:
                            diff = 2
                        elif cnt >= 2:
                            diff = 1
                            
                        dp[i][j] = min(dp[i][j], dp[l-1][j-d] +1 +diff)
                if j > 0:
                    # delete s[i]
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1])
        return dp[n][k]

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)

        @lru_cache(None)
        def dp(i, k, last, last_count):
            if (n - i) <= k:
                return 0 # remove all
            
            if s[i] == last:
                inc = 1 if last_count in [1,9,99] else 0
                return inc + dp(i + 1, k, last, last_count + 1)
            else:
                res = 1 + dp(i + 1, k, s[i], 1)
                if k:
                    res = min(res, dp(i + 1, k - 1, last, last_count))
                return res

        return dp(0, k, '', 0)


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def count(start, pre, pre_count, k):
            if k<0: return float('inf')
            if len(s)-start<=k: return 0
            
            if s[start]==pre:
                incr = 1 if pre_count==1 or pre_count==9 or pre_count==99 else 0
                return incr + count(start+1, pre, pre_count+1, k)
            else:
                delete = count(start+1, pre, pre_count, k-1)
                keep = 1 + count(start+1, s[start], 1, k)
                return min(delete, keep)
            
        return count(0, '', 0, k)


from collections import defaultdict
from functools import lru_cache


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # char2ids = defaultdict(list)
        # for i, c in enumerate(s):
        #     if len(char2ids[c]) == 0 or i > char2ids[c][-1] + 1:
        #         char2ids[c].append(i)

        def compressed_length(cnt):
            return 4 if cnt == 100 else (3 if cnt >= 10 else (2 if cnt > 1 else 1))

        @lru_cache(None)
        def DP(i, k):
            if k < 0: return float('inf')
            if i + 1 <= k: return 0

            ret = min(DP(i - 1, k) + 1, DP(i - 1, k - 1))
            cnt = 1
            for j in range(i - 1, -1, -1):
                if s[j] != s[i]:
                    k -= 1
                    if k < 0: break
                else:
                    cnt += 1
                    ret = min(DP(j - 1, k) + compressed_length(cnt), ret)

            return ret

        return DP(len(s) - 1, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        #dp[i][k] min len of s[i:] encoded by deleting at most k chars
        # delete d[i+1][k-1]
        # encode_len(s[i->j] == s[i]) + d(j+1, k - sum(s[i->j])) for j in range(i, n)
        n = len(s)
     
        @lru_cache(None)
        def dp(i, k):
            if k < 0: return n
            if i+k >= n:
                return 0
            res = dp(i+1, k-1)
            l = 0
            same = 0
            for j in range(i, n):
                if s[j] == s[i]:
                    same += 1
                    if same <= 2 or same == 10 or same == 100:
                        l += 1
                diff = j - i + 1 - same
                #if diff < 0: break
                res = min(res, l + dp(j+1, k - diff))
            return res
        
        return dp(0, k)
            



class Solution:
  def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
    n = len(s)
    dp_cache = dict()
    def dp(i, k):
      if k < 0:
        return n
      if i + k >= n:
        return 0

      if (i, k) in dp_cache:
        return dp_cache[(i, k)]
      ans = dp(i + 1, k - 1)
      l = 0
      same = 0
      for j in range(i, n):
        if s[j] == s[i]:
          same += 1
          if same <= 2 or same == 10 or same == 100:
            l += 1
        diff = j - i + 1 - same
        if diff < 0: break
        ans = min(ans, l + dp(j + 1, k - diff))
      dp_cache[(i, k)] = ans
      return ans
    return dp(0, k)

from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        def _len(cnt): return 1 if cnt == 1 else 2 if cnt <= 9 else 3 if cnt <= 99 else 4

        @lru_cache(None)
        def solve(left, k):
            if k < 0:
                return float('inf')
            # remove s[0:left+1]
            if left + 1 == k:
                return 0
            # 1. keep s[left]
            # 2. remove s[left]
            res = min(solve(left - 1, k) + 1, solve(left - 1, k - 1))
            cnt = 1
            for j in range(left - 1, -1, -1):
                if s[j] != s[left]:
                    k -= 1
                    if k < 0:
                        break
                else:
                    cnt += 1
                    if j < k:
                        break
                    res = min(res, solve(j - 1, k) + _len(cnt)) 
            return res
        return solve(len(s) - 1, k)


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def cmp(n):
            if n<=0:
                return 0
            if n==1:
                return 1
            if n<10:
                return 2
            if n>=100:
                return 4
            return 3
        
        @lru_cache(None)
        def solve(l,k):
            if k<0:
                return 10000
            if l>=len(s):
                return 0
            ans=solve(l+1,k-1)
            ad,de=0,0
            for i in range(l,len(s)):
                if s[i]==s[l]:
                    ad+=1
                else:
                    de+=1
                ans=min(ans,cmp(ad)+solve(i+1,k-de))
            # print(s[l:],k,ans)
            return ans
        
        return solve(0,k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        
        def backtrack(s, start, last, last_cnt, left, memo):
            if left < 0:
                return float('inf')
            
            if len(s) - start <= left:
                return 0
            
            if (start, last, last_cnt, left) in memo:
                return memo[(start, last, last_cnt, left)]
            
            ans = float('inf')
            if s[start] == last:
                if last_cnt == 1:
                    inc = 1
                else:
                    inc = len(str(last_cnt + 1)) - len(str(last_cnt))
                    
                ans = min(ans, inc + backtrack(s, start+1, last, last_cnt+1, left, memo))
            else:
                # delete
                delete_res = backtrack(s, start+1, last, last_cnt, left-1, memo)
                # keep
                keep_res = 1 + backtrack(s, start+1, s[start], 1, left, memo)
                
                ans = min(delete_res, keep_res)
                
            memo[(start, last, last_cnt, left)] = ans
            return memo[(start, last, last_cnt, left)]
        
        
        return backtrack(s, 0, '', 0, k, dict())
                


from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        if len(s) - k <= 1:
            return len(s) - k
        
        if len(s) == 100 and all([c==s[0] for c in s[1:]]):
            if k == 0: return 4
            if k <= 90: return 3
            if k <= 98: return 2
            return 1
        
        @lru_cache(None)
        def run(i, k, j, l):
            if k < 0:
                return 10000
            
            if i == len(s):
                return 0
            
            c = s[i]
            if c == j:
                return run(i+1, k, j, min(10, l+1)) + (l in [1,9]) 
            
            return min(
                run(i+1, k-1, j, l), 
                run(i+1, k, c, 1) + 1
            )
        return run(0, k, None, 0)


from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        
        @lru_cache(None)
        def dp(i, k, last, cnt):
            if k < 0:
                return float('inf')
            if i + k >= n:
                return 0
            res = n
            if last == s[i]:
                carry = int(cnt == 1 or cnt == 9 or cnt == 99)
                res = min(res, dp(i+1, k, last, cnt+1) + carry)
            else:
                res = min(res,
                         dp(i+1, k, s[i], 1) + 1,
                         dp(i+1, k-1, last, cnt))
            return res
        
        return dp(0, k, '', 0)


from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def dp(i, k, p, l):
            if k < 0: return sys.maxsize // 2
            if i >= len(s): return 0
            
            if s[i] == p:
                carry = l in [1, 9, 99]
                return carry + dp(i+1, k, p, l+1)
            else: # min(delete s[i], keep s[i])
                return min(dp(i+1, k-1, p, l),
                          1 + dp(i+1, k, s[i], 1))
        return dp(0, k, '', 0)


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        #if s[i] != s[i-1]: dp[i][t] = min(dp[i-1][t-1], dp[i-1][t] + 1)
        #else: dp[i][t] = min(dp[i-1][t-1], dp[i-1][t] + carry) carry = (cnt in [9, 99, 999]) cnt += 1
        n = len(s)
        cp = s[:]
        @lru_cache(None)
        def dp(i, last, curlen, k):
            if k < 0: return n+1
            if i >= n:
                return 0
            res = n+1
            if s[i] == last:
                carry = (curlen in [1, 9, 99])
                res = carry + dp(i+1, last, curlen+1, k)
            else:
                res = min(1+ dp(i+1, s[i], 1, k),
                         dp(i+1, last, curlen, k-1))
            return res
        
        return dp(0, '.', 0, k)
            


from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def dp(i, k, p, l): # p: last char from prev step, l: len(last char) of prev step
            # delete
            if k < 0: return sys.maxsize // 2
            if i >= len(s): return 0            
            if s[i] == p: # same as prev, no need to delete
                carry = l in [1, 9, 99]
                return carry + dp(i+1, k, p, l+1)
            else:
                return min(1 + dp(i+1, k, s[i], 1), # keep s[i]
                        dp(i+1, k-1, p, l)
                         )
        return dp(0, k, '', 0)


def dlen(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans


def backtrack(i, s, k, memo):
    n = len(s)
    if k < 0:
        return float('inf')
    elif i == n or k >= n - i: # empty
        return 0
    elif (i, k) in memo:
        return memo[(i, k)]
    else:
        ans = float('inf')
        count = defaultdict(int)
        most_freq = 0

        for j in range(i, n):
            char = s[j]
            count[char] += 1
            most_freq = max(most_freq, count[char])
            digit_len = 0 if most_freq == 1 else len(str(most_freq))
            range_length = j - i + 1
            ans = min(ans, 1 + digit_len + backtrack(j + 1, s, k - (range_length - most_freq), memo))
        memo[(i, k)] = ans
        return ans
        
        
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # dp[i][j]
        # denotes minimum length of encoded string from 0 to i with at most j deletion
        # Transition:
        # if we keep s[i]: 
        # dp[i][j] = dp[i - 1][j - 1]
        # if we remove s[i]:
        # dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len for p from i..0)
        
        n = len(s)
        memo = {}
        return backtrack(0, s, k, memo)
#         dp = [[float('inf') for _ in range(k + 1)] for _ in range(n + 1)]
        
#         for j in range(k + 1):
#             dp[0][j] = 0
        
#         # we have two choices, to remove s[i] or to keep s[i]
#         for i in range(1, n + 1):
#             for j in range(k + 1):
#                 if j > 0:
#                     # remove current character
#                     dp[i][j] = dp[i - 1][j - 1]
                
#                 # also consider remove the least frequent characters before s[i]
#                 removed = 0
#                 count = 0
#                 for p in range(i, 0, -1):
#                     if s[i - 1] == s[p - 1]:
#                         count += 1
#                     else:
#                         removed += 1
                    
#                     # remove at most j, cannot exceed j
#                     if removed > j:
#                         break
                    
#                     digit_len = 0 if count == 1 else dlen(count)
#                     dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len)
                
#         return dp[n][k]
        
        


from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        if len(s) - k <= 1:
            return len(s)-k
        
        @lru_cache(None)
        def run(i, j, k, l):
            if k < 0:
                return 10000
            
            if i == len(s):
                return 0
            
            c = s[i]
            if c == j:
                return run(i+1, c, k, l+1) + (1 if l in [1, 9, 99] else 0)
            
            return min(
                run(i+1, j, k-1, l),
                run(i+1, c, k, 1) + 1,
            )
        
        return run(0, None, k, 0)


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def counter(start,last,last_cnt,left):
            if left < 0:
                return float('inf')
            if start >= len(s):
                return 0
            if s[start] == last:
                inc = 1 if last_cnt == 1 or last_cnt == 9 or last_cnt == 99 else 0
                return inc + counter(start+1,last,last_cnt+1,left)
            else:
                keep_c = 1 + counter(start+1,s[start],1,left)
                del_c = counter(start+1,last,last_cnt,left-1)
                return min(keep_c,del_c)
        return counter(0,'',0,k)

def dlen(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans


def backtrack(i, s, k, memo):
    n = len(s)
    
    if k < 0:
        return float('inf')
    elif i == n or k >= n - i: # empty
        return 0
    elif (i, k) in memo:
        return memo[(i, k)]
    else:
        ans = float('inf')
        count = defaultdict(int)
        most_freq = 0

        for start in range(i, n):
            char = s[start]
            count[char] += 1
            most_freq = max(most_freq, count[char])
            digit_len = 0 if most_freq == 1 else len(str(most_freq))

            ans = min(ans, 1 + digit_len + backtrack(start + 1, s, k - (start - i + 1 - most_freq), memo))
        
        memo[(i, k)] = ans
        return ans
        
        
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # dp[i][j]
        # denotes minimum length of encoded string from 0 to i with at most j deletion
        # Transition:
        # if we keep s[i]: 
        # dp[i][j] = dp[i - 1][j - 1]
        # if we remove s[i]:
        # dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len for p from i..0)
        
        n = len(s)
        memo = {}
        return backtrack(0, s, k, memo)
#         dp = [[float('inf') for _ in range(k + 1)] for _ in range(n + 1)]
        
#         for j in range(k + 1):
#             dp[0][j] = 0
        
#         # we have two choices, to remove s[i] or to keep s[i]
#         for i in range(1, n + 1):
#             for j in range(k + 1):
#                 if j > 0:
#                     # remove current character
#                     dp[i][j] = dp[i - 1][j - 1]
                
#                 # also consider remove the least frequent characters before s[i]
#                 removed = 0
#                 count = 0
#                 for p in range(i, 0, -1):
#                     if s[i - 1] == s[p - 1]:
#                         count += 1
#                     else:
#                         removed += 1
                    
#                     # remove at most j, cannot exceed j
#                     if removed > j:
#                         break
                    
#                     digit_len = 0 if count == 1 else dlen(count)
#                     dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len)
                
#         return dp[n][k]
        
        


from functools import lru_cache

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def compress(now, prev_ch, prev_count, left):
            if left < 0: return len(s) + 1
            if now >= len(s): return 0
            if s[now] == prev_ch:
                incr = 1 if prev_count == 1 or prev_count == 9 or prev_count == 99 else 0
                return incr + compress(now + 1, prev_ch, prev_count + 1, left)
            keep = 1 + compress(now + 1, s[now], 1, left)
            delete = compress(now + 1, prev_ch, prev_count, left - 1)
            return min(keep, delete)
        
        return compress(0, '', 0, k)

from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        def _len(cnt): return 1 if cnt == 1 else 2 if cnt <= 9 else 3 if cnt <= 99 else 4

        @lru_cache(None)
        def solve(left, k):
            if k < 0:
                return float('inf')
            # remove s[0:left+1]
            if left + 1 == k:
#                 print(93, left -1, k )
                return 0
            # 1. keep s[left], regard no repeating
            # 2. remove s[left]
            res = min(solve(left - 1, k) + 1, solve(left - 1, k - 1))
#             print(98, left -1, k )
            # 3. fix repeating characters
            cnt = 1
            for j in range(left - 1, -1, -1):
                if j < k:
                    break
                elif s[j] != s[left]:
                    k -= 1
                else:
                    cnt += 1
                    res = min(res, solve(j - 1, k) + _len(cnt)) 
#                 print(110, j -1, k )
            return res
        return solve(len(s) - 1, k)


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def dp(start, last, lastCount, k):
            if k < 0:
                return float('inf')
            if start == len(s):
                return 0
            if s[start] == last:
                inc = 1 if lastCount == 1 or lastCount == 9 or lastCount == 99 else 0
                return inc + dp(start+1, last, lastCount + 1, k)
            else:
                return min(dp(start+1, last, lastCount, k-1), 1 + dp(start+1, s[start], 1, k))
        return dp(0, '', 0, k)

from functools import lru_cache

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
            
        @lru_cache(None)
        def dfs(start, last_ch, count, k):
            if k < 0:
                return float('inf')
            if start >= len(s):
                return 0
            if s[start] == last_ch:
                return dfs(start+1, last_ch, count+1, k) + ( 1 if count in {1, 9, 99, 99} else 0 )
            else:
                keep = 1 + dfs(start+1, s[start], 1, k)
                discard = dfs(start+1, last_ch, count, k - 1)
                return min(keep, discard)
        
        return dfs(0, '', 0, k)


from functools import lru_cache

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def compress(now, prev_ch, prev_count, left):
            if left < 0: return len(s) + 1
            if now >= len(s): return 0
            if s[now] == prev_ch:
                incr = 1 if prev_count == 1 or prev_count == 9 or prev_count == 99 else 0
                return incr + compress(now + 1, s[now], prev_count + 1, left)
            keep = 1 + compress(now + 1, s[now], 1, left)
            delete = compress(now + 1, prev_ch, prev_count, left - 1)
            return min(keep, delete)
        
        return compress(0, '', 0, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        def _len(cnt): return 1 if cnt == 1 else 1 + len(str(cnt))
        dp = [[0]*(k+1) for _ in range(len(s)+1)]

        for ki in range(k+1):
            for left in range(ki, len(s)):
                drop = dp[left-1][ki-1] if ki > 0 else float('inf')
                keep = 1 + dp[left-1][ki]
                cnt = 1
                kj = ki
                for j in range(left-1, -1, -1):
                    if s[j] != s[left]:
                        if kj == 0:
                            break
                        kj -= 1
                    else:
                        cnt += 1
                        keep = min(keep, _len(cnt) + dp[j-1][kj])

                dp[left][ki] = min(keep, drop)

        return dp[len(s)-1][k]


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        
        def calculatelen(cnt):         #length calculator
            if cnt==0: return 0
            elif cnt==1: return 1
            elif cnt < 10: return 2
            elif cnt < 100: return 3
            else: return 4
        
        
        n = len(s)
        x = 999999
        dp = [[x]*(k+1) for i in range(n+1)]
        for i in range(k+1):
            dp[0][i] = 0

        for i in range(1,n+1):
            for j in range(k+1):
                
                cnt,remove = 0,0
                
                if j > 0: dp[i][j] = dp[i-1][j-1]
                    
                for p in range(i,0,-1):
                    if(s[p-1] == s[i-1]): cnt+=1
                    else: 
                        remove += 1
                        if remove > j: break
                    dp[i][j] = min(dp[i][j],(dp[p-1][j-remove] + calculatelen(cnt)))
                    
        return dp[n][k]

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        N = len(s)
        
        @lru_cache(None)
        def rec(cur, rem, ln, ch):
            if rem < 0:
                return math.inf
            if cur == N:
                return 0
            
            ans = math.inf
            if s[cur] == ch:
                add = (ln == 1 or ln == 9 or ln == 99)
                ans = rec(cur+1, rem, ln + 1, ch) + add
            else:
                ans = rec(cur+1, rem-1, ln, ch)
                ans = min(ans, rec(cur+1, rem, 1, s[cur]) + 1)
            
            return ans
        
        return rec(0, k, 0, '')


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def dp(start, last, lastCount, k):
            if k < 0:
                return float('inf')
            if start == len(s):
                return 0
            if s[start] == last:
                inc = 1 if lastCount == 1 or lastCount == 9 or lastCount == 99 else 0
                return min(inc + dp(start+1, last, lastCount + 1, k), 1 + dp(start+1, last, 1, k-1))
            else:
                return min(dp(start+1, last, lastCount, k-1), 1 + dp(start+1, s[start], 1, k))
        return dp(0, '', 0, k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        #if s[i] != s[i-1]: dp[i][t] = min(dp[i-1][t-1], dp[i-1][t] + 1)
        #else: dp[i][t] = min(dp[i-1][t-1], dp[i-1][t] + carry) carry = (cnt in [9, 99, 999]) cnt += 1
        n = len(s)
        cp = s[:]
        
        dp = [[n+1]*(k+2) for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1, n+1):
            for t in range(k+1):
                dp[i][t+1] = min(dp[i-1][t], dp[i][t+1])
                cnt = 0
                delete = 0
                for l in range(i, n+1):
                    if (cp[i-1] == cp[l-1]):
                        cnt += 1
                    else:
                        delete += 1
                    if (t + delete <= k):
                        leng = dp[i-1][t] + 1
                        if cnt >= 100: leng += 3
                        elif cnt >= 10: leng += 2
                        elif cnt >= 2: leng += 1
                        else: leng += 0
                        dp[l][t+delete] = min(dp[l][t+delete], leng)
                    else:
                        break
        return dp[n][k]

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        
        def calc(l):
            if l == 0: return 0
            elif l == 1: return 1
            elif l < 10: return 2
            elif l < 100: return 3
            return 4
        
        
        dp = [[float('inf')]*(k+1) for _ in range(len(s)+1)]
        
        for i in range(k+1):
            dp[0][i] = 0
            
        
        for i in range(1, len(s)+1):
            for j in range(0, k+1):
                # print(\"{0} {1}\".format(i,j))
                if j > 0:
                    dp[i][j] = dp[i-1][j-1]
                
                rem, cnt = 0, 0
                for p in range(i, 0, -1):
                    if s[p-1] == s[i-1]:
                        cnt+=1
                    else:
                        rem+=1
                    
                    if rem > j:
                        break
                
                    dp[i][j] = min(dp[i][j],
                              dp[p-1][j-rem]+calc(cnt))
        
        # for row in dp:
        #     print(row)
        
        return dp[len(s)][k]


from functools import lru_cache
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @lru_cache(None)
        def min_run_len(last_char, last_count, curr_idx, rest_k):
            if curr_idx == len(s):
                return 0
            
            # Keep current char
            curr_count = last_count + 1 if s[curr_idx] == last_char else 1
            incr = 1 if curr_count in [1, 2, 10, 100] else 0
            res1 = incr + min_run_len(s[curr_idx], curr_count, curr_idx + 1, rest_k)
            
            # Delete current char
            res2 = float('inf')
            if rest_k > 0:
                res2 = min_run_len(last_char, last_count, curr_idx + 1, rest_k - 1)
                
            return min(res1, res2)
        
        return min_run_len('#', 0, 0, k)


import functools

class Solution:
    @functools.lru_cache(maxsize = None)
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        @functools.lru_cache(maxsize = None)
        def dp(i: int, last: int, size: int, k: int) -> int:
            if k < 0:
                return float('inf')
            if i >= len(s):
                return 0
            answer: int = 0
            if ord(s[i]) - ord('a') == last:
                # same as the previous character, no need to delete
                carry: int = 1 if size in (1, 9, 99) else 0
                answer = carry + dp(i + 1, last, size + 1, k)
            else:
                # answer = min(keep s[i], delete s[i])
                answer = min(1 + dp(i + 1, ord(s[i]) - ord('a'), 1, k), dp(i + 1, last, size, k - 1))
            return answer
        return dp(0, 26, 0, k)

class Solution:
    
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        
        def calculatelen(cnt):         #length calculator
            if cnt==0: return 0
            elif cnt==1: return 1
            elif cnt < 10: return 2
            elif cnt < 100: return 3
            else: return 4
        
        
        n = len(s)
        x = 999999
        dp = [[x]*(k+1) for i in range(n+1)]
        for i in range(k+1):
            dp[0][i] = 0

        for i in range(1,n+1):
            for j in range(k+1):
                
                cnt,remove = 0,0
                
                if j > 0: dp[i][j] = dp[i-1][j-1]
                    
                for p in range(i,0,-1):
                    if(s[p-1] == s[i-1]): cnt+=1
                    else: 
                        remove += 1
                        if remove > j: break
                    dp[i][j] = min(dp[i][j],(dp[p-1][j-remove] + calculatelen(cnt)))
                    
        return dp[n][k]

def dlen(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # dp[i][j]
        # denotes minimum length of encoded string from 0 to i with at most j deletion
        # Transition:
        # if we keep s[i]: 
        # dp[i][j] = dp[i - 1][j - 1]
        # if we remove s[i]:
        # dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len for p from i..0)
        
        n = len(s)
        dp = [[float('inf') for _ in range(k + 1)] for _ in range(n + 1)]
        
        for j in range(k + 1):
            dp[0][j] = 0
        
        # we have two choices, to remove s[i] or to keep s[i]
        for i in range(1, n + 1):
            for j in range(k + 1):
                if j > 0:
                    # remove current character
                    dp[i][j] = dp[i - 1][j - 1]
                
                # also consider remove all least frequent characters before s[i]
                removed = 0
                count = 0
                for p in range(i, 0, -1):
                    if s[i - 1] == s[p - 1]:
                        count += 1
                    else:
                        removed += 1
                    
                    # remove at most j, cannot exceed j
                    if removed > j:
                        break
                    
                    digit_len = 0 if count == 1 else dlen(count)
                    dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len)
        
        return dp[n][k]
        
        


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        st,n = 0,len(s)
        seg = []
        for i in range(1,n):
            if s[i]!=s[i-1]:
                seg.append((s[i-1],i-st))
                st=i
        seg.append((s[n-1],n-st))
        n=len(seg)
        dp = [[None]*(k+1) for _ in range(n)]
        def solve(i,ki):
            if i==n:
                return 0
            if dp[i][ki] is not None:
                return dp[i][ki]
            dp[i][ki]=float('inf')
            for j in range(min(ki+1,seg[i][1]+1)):
                if seg[i][1]!=j:
                    dp[i][ki]=min(dp[i][ki],1+(len(str(seg[i][1]-j)) if seg[i][1]-j!=1 else 0)+solve(i+1,ki-j))
                else:
                    dp[i][ki]=min(dp[i][ki],solve(i+1,ki-j))
            ps = 0
            curr=0
            for j in range(i+1,n):
                if ki>=ps and seg[j][0]==seg[i][0]:
                    for kj in range(ki-ps+1):
                        if kj<seg[i][1]+seg[j][1]+curr:
                            dp[i][ki]=min(dp[i][ki],1+(len(str(seg[i][1]+curr+seg[j][1]-kj)) if seg[i][1]+curr+seg[j][1]-kj!=1 else 0)+solve(j+1,ki-ps-kj))
                        elif kj==seg[i][1]+seg[j][1]+curr:
                            dp[i][ki]=min(dp[i][ki],solve(j+1,ki-ps-kj))
                        else:
                            break
                ps+=(seg[j][1] if seg[j][0]!=seg[i][0] else 0)
                curr+=(seg[j][1] if seg[j][0]==seg[i][0] else 0)
            return dp[i][ki]
        return solve(0,k)

def dlen(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # dp[i][j]
        # denotes minimum length of encoded string from 0 to i with at most j deletion
        # Transition:
        # if we keep s[i]: 
        # dp[i][j] = dp[i - 1][j - 1]
        # if we remove s[i]:
        # dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len for p from i..0)
        
        n = len(s)
        dp = [[float('inf') for _ in range(k + 1)] for _ in range(n + 1)]
        
        for j in range(k + 1):
            dp[0][j] = 0
        
        # we have two choices, to remove s[i] or to keep s[i]
        for i in range(1, n + 1):
            for j in range(k + 1):
                if j > 0:
                    # remove current character
                    dp[i][j] = dp[i - 1][j - 1]
                
                # also consider remove the least frequent characters before s[i]
                removed = 0
                count = 0
                for p in range(i, 0, -1):
                    if s[i - 1] == s[p - 1]:
                        count += 1
                    else:
                        removed += 1
                    
                    # remove at most j, cannot exceed j
                    if removed > j:
                        break
                    
                    digit_len = 0 if count == 1 else dlen(count)
                    dp[i][j] = min(dp[i][j], dp[p - 1][j - removed] + 1 + digit_len)
        
        return dp[n][k]
        
        


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        
        #index,last_char,running_length, k
        
        @lru_cache(None)
        def dp(index, last_char, running_length,k):
            if index >= len(s):
                return 0
            if k < 0:
                return 9999999
            if s[index] == last_char:
                extra = 0
                if running_length == 1 or running_length == 9 or running_length == 99:
                    extra += 1
                incl = extra + dp(index+1,s[index],running_length+1,k)
                excl = 99999
                if k > 0:
                    excl = dp(index+1,last_char,running_length,k-1)
                return min(incl,excl)
            incl = 1 + dp(index+1,s[index],1,k)
            excl = 99999
            if k > 0:
                excl = dp(index+1,last_char,running_length,k-1)
            return min(incl,excl)
        return dp(0,'',0,k)