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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

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):
			if n - i <= k:
				return {}
			(x, res) = (s[i], {})
			if k:
				res = dp(i + 1, k - 1)
			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')
			if left + 1 == k:
				return 0
			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
			ans = get_compressed_len(left_count + 1) + dp_memo(x + 1, y, 0, remain_k)
			if remain_k > 0:
				ans = min(ans, get_compressed_len(left_count) + dp_memo(x + 1, y, 0, remain_k - 1))
			for i in range(remain_k + 1):
				xx = x + i + 1
				if xx > y:
					break
				if s[x] == s[xx]:
					ans = min(ans, dp_memo(xx, y, left_count + 1, remain_k - i))
			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 = {(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():
				if deletions < k:
					new_state = (deletions + 1, last_char, count)
					new_length = length
					new_states[new_state] = min(new_states[new_state], new_length)
				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])
				take = 0
				for k in range(i + 1)[::-1]:
					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:

		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))):
					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 1000000.0
			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:

		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):
					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:
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
		return dp[n][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), 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:
					if k > 0:
						ans = min(ans, process(i - 1, x, c, k - 1))
					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_len = 1 + counter(start + 1, s[start], 1, rem_chars)
					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):
			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)
			return (prevsum, curchar, curlen)

		@lru_cache(None)
		def dp(code, remain, todel, curchar, curlen: int):
			if remain == todel:
				return singlelen(curlen)
			if todel == 0:
				(prelen, curchar, curlen) = add(curchar, curlen, code)
				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]:
				cases.append(dp(code[1:], remain - code[0][1], todel - code[0][1], curchar, curlen))
			(prelen, newchar, newlen) = add(curchar, curlen, code[:1])
			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))
			if len(cases) == 0:
				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:
		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:
					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
			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:

		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:
		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
				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)


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))
			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_res = backtrack(s, start + 1, last, last_cnt, left - 1, memo)
				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:
				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:
		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)


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:
		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:
		n = len(s)
		memo = {}
		return backtrack(0, s, k, memo)


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)


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)


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)


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):
			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:
		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):
				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))
		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
			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)
			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:
				carry: int = 1 if size in (1, 9, 99) else 0
				answer = carry + dp(i + 1, last, size + 1, k)
			else:
				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)


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

class Solution:

	def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
		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
		for i in range(1, n + 1):
			for j in range(k + 1):
				if j > 0:
					dp[i][j] = dp[i - 1][j - 1]
				removed = 0
				count = 0
				for p in range(i, 0, -1):
					if s[i - 1] == s[p - 1]:
						count += 1
					else:
						removed += 1
					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)


class Solution:

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

		@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)