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

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

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

16
    if (keyVal != null) {
17
      return keyVal;
18
    }
19
    char ch = s.charAt(index);
20
    int count = 1;
21
    int nextIndex = index + 1;
22

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

25
      if (s.charAt(i) == ch) {
26
        count++;
27
        nextIndex = i + 1;
28
      } else {
29
        nextIndex = i;
30
        break;
31
      }
32
    }
33
    int totalCount = count;
34
    int prevCountRepresentation = 0;
35
    // if prev char is equal to current char that means we have removed middle element
36
    // So we have to subtract the previous representation length and add the new encoding
37
    // representation length
38
    if (ch == prevChar) {
39
      totalCount += prevCharCount;
40
      prevCountRepresentation = getLength(prevCharCount);
41
    }
42

43
    int representaionLength = getLength(totalCount);
44
    int ans =
45
        representaionLength
46
            + recur(s, ch, totalCount, k, nextIndex, memo)
47
            - prevCountRepresentation;
48

49
    if (k > 0) {
50

51
      for (int i = 1; i <= k && i <= count; i++) {
52
        int currentCount = totalCount - i;
53
        int length = getLength(currentCount);
54
        // checking if we have to send current char and current char count or previous char
55
        // and previous char count
56
        int holder =
57
            length
58
                + recur(
59
                    s,
60
                    currentCount == 0 ? prevChar : ch,
61
                    currentCount == 0 ? prevCharCount : currentCount,
62
                    k - i,
63
                    nextIndex,
64
                    memo)
65
                - prevCountRepresentation;
66
        ans = Math.min(ans, holder);
67
      }
68
    }
69
    memo.put(key, ans);
70
    return ans;
71
  }
72

73
  // Since length for aaaaa will be a5(2) aaaaaaaaaa a10(3) etc.
74
  private int getLength(int n) {
75

76
    if (n == 0) {
77
      return 0;
78
    } else if (n == 1) {
79
      return 1;
80
    } else if (n < 10) {
81
      return 2;
82
    } else if (n < 100) {
83
      return 3;
84
    } else {
85
      return 4;
86
    }
87
  }
88
}