class Solution {
 public:
  int getLengthOfOptimalCompression(string s, int k) {
    // dp[i][k] := length of optimal compression of s[i:] w/ at most k deletion
    dp.resize(s.length(), vector<int>(k + 1, kMax));
    return compression(s, 0, k);
  }

 private:
  constexpr static int kMax = 101;
  vector<vector<int>> dp;

  int compression(const string& s, int i, int k) {
    if (k < 0)
      return kMax;
    if (i == s.length() || s.length() - i <= k)
      return 0;
    if (dp[i][k] != kMax)
      return dp[i][k];

    int maxFreq = 0;  // max freq in s[i..j]
    vector<int> count(128);

    // make chars in s[i..j] be same
    // keep the char that has max freq in this range and remove other chars
    for (int j = i; j < s.length(); ++j) {
      maxFreq = max(maxFreq, ++count[s[j]]);
      dp[i][k] = min(dp[i][k],
                     getLength(maxFreq) +
                     compression(s, j + 1, k - (j - i + 1 - maxFreq)));
    }

    return dp[i][k];
  }

  int getLength(int maxFreq) {  // the length to compress `maxFreq`
    if (maxFreq == 1)
      return 1;  // c
    if (maxFreq < 10)
      return 2;  // [1-9]c
    if (maxFreq < 100)
      return 3;  // [1-9][0-9]c
    return 4;    // [1-9][0-9][0-9]c
  }
};

class Solution {
  public int getLengthOfOptimalCompression(String s, int k) {
    // dp[i][k] := length of optimal compression of s[i:] w/ at most k deletion
    dp = new int[s.length()][k + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, kMax));
    return compression(s, 0, k);
  }

  private static final int kMax = 101;
  private int[][] dp;

  private int compression(final String s, int i, int k) {
    if (k < 0)
      return kMax;
    if (i == s.length() || s.length() - i <= k)
      return 0;
    if (dp[i][k] != kMax)
      return dp[i][k];

    int maxFreq = 0;
    int[] count = new int[128];

    for (int j = i; j < s.length(); ++j) {
      maxFreq = Math.max(maxFreq, ++count[s.charAt(j)]);
      dp[i][k] = Math.min(dp[i][k],
                          getLength(maxFreq) +
                          compression(s, j + 1, k - (j - i + 1 - maxFreq)));
    }

    return dp[i][k];
  }

  private int getLength(int maxFreq) { // the length to compress `maxFreq`
    if (maxFreq == 1)
      return 1; // c
    if (maxFreq < 10)
      return 2; // [1-9]c
    if (maxFreq < 100)
      return 3; // [1-9][0-9]c
    return 4;   // [1-9][0-9][0-9]c
  }
}

class Solution:
  def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
    def getLength(maxFreq):  # the length to compress `maxFreq`
      if maxFreq == 1:
        return 1  # c
      if maxFreq < 10:
        return 2  # [1-9]c
      if maxFreq < 100:
        return 3  # [1-9][0-9]c
      return 4    # [1-9][0-9][0-9]c

    # compression(i, k) := length of optimal compression of s[i:] w/ at most k deletion
    @lru_cache(None)
    def compression(i, k):
      if k < 0:
        return math.inf
      if i == len(s) or len(s) - i <= k:
        return 0

      ans = math.inf
      maxFreq = 0  # max freq in s[i..j]
      count = Counter()

      # make chars in s[i..j] be same
      # keep the char that has max freq in this range and remove other chars
      for j in range(i, len(s)):
        count[s[j]] += 1
        maxFreq = max(maxFreq, count[s[j]])
        ans = min(ans, getLength(maxFreq) +
                  compression(j + 1, k - (j - i + 1 - maxFreq)))

      return ans

    return compression(0, k)