Run-length encoding is a string compression method that works by&nbsp;replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string&nbsp;"aabccc"&nbsp;we replace "aa"&nbsp;by&nbsp;"a2"&nbsp;and replace "ccc"&nbsp;by&nbsp;"c3". Thus the compressed string becomes "a2bc3".

Notice that in this problem, we are not adding&nbsp;'1'&nbsp;after single characters.

Given a&nbsp;string s&nbsp;and an integer k. You need to delete at most&nbsp;k characters from&nbsp;s&nbsp;such that the run-length encoded version of s&nbsp;has minimum length.

Find the minimum length of the run-length encoded&nbsp;version of s after deleting at most k characters.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 100
	0 &lt;= k &lt;= s.length
	s contains only lowercase English letters.


class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # Find min lenth of the code starting from group ind, if there are res_k characters to delete and
        # group ind needs to be increased by carry_over additional characters
        def FindMinLen(ind, res_k, carry_over=0):

            # If we already found the min length - just retrieve it (-1 means we did not calculate it)
            if carry_over == 0 and dynamic[ind][res_k] != -1:
                return dynamic[ind][res_k]

            # Number of character occurences that we need to code. Includes carry-over.
            cur_count = carry_over + frequency[ind]

            # Min code length if the group ind stays intact. The code accounts for single-character "s0" vs. "s" situation.
            min_len = 1 + min(len(str(cur_count)), cur_count - 1) + FindMinLen(ind+1,res_k)

            # Min length if we keep only 0, 1, 9, or 99 characters in the group - delete the rest, if feasible
            for leave_count, code_count in [(0,0), (1, 1), (9, 2), (99, 3)]:
                if cur_count > leave_count and res_k >= cur_count - leave_count:
                    min_len = min(min_len, code_count + FindMinLen(ind + 1,res_k - (cur_count - leave_count)))

            # If we drop characters between this character group and next group, like drop "a" in "bbbabb"
            next_ind = chars.find(chars[ind], ind + 1)
            delete_count = sum(frequency[ind+1:next_ind])
            if next_ind > 0 and res_k >= delete_count:
                min_len = min(min_len, FindMinLen(next_ind, res_k - delete_count, carry_over = cur_count))

            # If there was no carry-over, store the result
            if carry_over == 0: dynamic[ind][res_k] = min_len
            return min_len

        # Two auxiliary lists - character groups (drop repeated) and number of characters in the group
        frequency, chars = [], ""
        for char in s:
            if len(frequency)==0 or char != chars[-1]:
                frequency.append(0)
                chars = chars + char
            frequency[-1] += 1

        # Table with the results. Number of character groups by number of available deletions.
        dynamic = [[-1] * (k + 1) for i in range(len(frequency))] + [[0]*(k + 1)]

        return FindMinLen(0, k)
class Solution {
	 public int getLengthOfOptimalCompression(String s, int k) {
        Map<String, Integer> memo = new HashMap<>();
        return recur(s, '\u0000', 0, k, 0, memo);
    }

    private int recur(String s, char prevChar, int prevCharCount, int k, int index, Map<String, Integer> memo) {

        if (index == s.length()) {
            return 0;
        }
        String key = prevChar + ", " + prevCharCount + ", " + k + ", " + index;
        Integer keyVal = memo.get(key);

        if (keyVal != null) {
            return keyVal;
        }
        char ch = s.charAt(index);
        int count = 1;
        int nextIndex = index + 1;

        for (int i = index + 1; i < s.length(); i++) {

            if (s.charAt(i) == ch) {
                count++;
                nextIndex = i + 1;
            } else {
                nextIndex = i;
                break;
            }
        }
        int totalCount = count;
        int prevCountRepresentation = 0;
        //if prev char is equal to current char that means we have removed middle element
        //So we have to subtract the previous representation length and add the new encoding
        //representation length
        if (ch == prevChar) {
            totalCount += prevCharCount;
            prevCountRepresentation = getLength(prevCharCount);
        }

        int representaionLength = getLength(totalCount);
        int ans = representaionLength + recur(s, ch, totalCount, k, nextIndex, memo) - prevCountRepresentation;

        if (k > 0) {

            for (int i = 1; i <= k && i <= count; i++) {
                int currentCount = totalCount - i;
                int length = getLength(currentCount);
                //checking if we have to send current char and current char count or previous char
                //and previous char count
                int holder = length + recur(s, currentCount == 0 ? prevChar : ch,
                        currentCount == 0 ? prevCharCount : currentCount, k - i, nextIndex, memo) -
                        prevCountRepresentation;
                ans = Math.min(ans, holder);
            }
        }
        memo.put(key, ans);
        return ans;
    }
    //Since length for aaaaa will be a5(2) aaaaaaaaaa a10(3) etc.
    private int getLength(int n) {

        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (n < 10) {
            return 2;
        } else if (n < 100) {
            return 3;
        } else  {
            return 4;
        }
    }
}
class Solution {
public:
    int dp[101][101];
    int dfs(string &s, int left, int K) {
        int k = K;
        if(s.size() - left <= k) return 0;
        if(dp[left][k] >= 0) return dp[left][k];
        int res = k ? dfs(s, left + 1, k - 1) : 10000, c = 1;
        for(int i = left + 1; i <= s.size(); ++i) {
            res = min(res, dfs(s, i, k) + 1 + (c >= 100 ? 3 : (c >= 10 ? 2 : (c > 1 ? 1 :0))));
            if(i == s.size()) break;
            if(s[i] == s[left]) ++c;
            else if(--k < 0) break;
        }
        return dp[left][K] = res;
    }
    
    int getLengthOfOptimalCompression(string s, int k) {
        memset(dp, -1, sizeof(dp));
        return dfs(s, 0, k);
    }
};
var getLengthOfOptimalCompression = function(s, k) {
    const memo = new Map()
    
    const backtrack = (i, lastChar, lastCharCount, k) => {
        if (k < 0) return Number.POSITIVE_INFINITY
        if (i >= s.length) return 0
        
        const memoKey = `${i}#${lastChar}#${lastCharCount}#${k}`
        if (memoKey in memo) return memo[memoKey]
        
        if (s[i] === lastChar) {
            const incrementor = [1, 9, 99].includes(lastCharCount) ? 1 : 0
            memo[memoKey] = incrementor + backtrack(i+1, lastChar, lastCharCount+1, k)
        } else {
            memo[memoKey] = Math.min(
                1 + backtrack(i+1, s[i], 1, k), //keep char
                backtrack(i+1, lastChar, lastCharCount, k-1) //delete char
            )
        }
        return memo[memoKey]
    }
    return backtrack(0, '', 0, k)
};
String Compression II