1
var getLengthOfOptimalCompression = function (s, k) {
2
  const memo = new Map();
3

4
  const backtrack = (i, lastChar, lastCharCount, k) => {
5
    if (k < 0) return Number.POSITIVE_INFINITY;
6
    if (i >= s.length) return 0;
7

8
    const memoKey = `${i}#${lastChar}#${lastCharCount}#${k}`;
9
    if (memoKey in memo) return memo[memoKey];
10

11
    if (s[i] === lastChar) {
12
      const incrementor = [1, 9, 99].includes(lastCharCount) ? 1 : 0;
13
      memo[memoKey] =
14
        incrementor + backtrack(i + 1, lastChar, lastCharCount + 1, k);
15
    } else {
16
      memo[memoKey] = Math.min(
17
        1 + backtrack(i + 1, s[i], 1, k), //keep char
18
        backtrack(i + 1, lastChar, lastCharCount, k - 1) //delete char
19
      );
20
    }
21
    return memo[memoKey];
22
  };
23
  return backtrack(0, "", 0, k);
24
};