• Time:O(n^2k)
• Space:O(nk)

## 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.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
}
};
``````

## JAVA

``````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
}
}
``````

## Python

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