String Compression II
Problem
Given a string s and integer k, delete at most k characters so that the run-length encoded form of the resulting string is as short as possible. Return that minimum length.
s = "aaabcccd", k = 24from functools import lru_cache
def get_length_of_optimal_compression(s, k):
n = len(s)
def enc(x):
if x == 1: return 1
if x < 10: return 2
if x < 100: return 3
return 4
@lru_cache(maxsize=None)
def dp(i, k):
if k < 0: return float('inf')
if i == n: return 0
best = dp(i + 1, k - 1) # delete s[i]
cnt, deleted = 0, 0
for j in range(i, n):
if s[j] == s[i]: cnt += 1
else: deleted += 1
if deleted > k: break
best = min(best, enc(cnt) + dp(j + 1, k - deleted))
return best
return dp(0, k)function getLengthOfOptimalCompression(s, k) {
const n = s.length;
const memo = new Map();
function enc(x) { return x === 1 ? 1 : x < 10 ? 2 : x < 100 ? 3 : 4; }
function dp(i, k) {
if (k < 0) return Infinity;
if (i === n) return 0;
const key = i * 110 + k;
if (memo.has(key)) return memo.get(key);
let best = dp(i + 1, k - 1);
let cnt = 0, del = 0;
for (let j = i; j < n; j++) {
if (s[j] === s[i]) cnt++; else del++;
if (del > k) break;
best = Math.min(best, enc(cnt) + dp(j + 1, k - del));
}
memo.set(key, best);
return best;
}
return dp(0, k);
}class Solution {
int n; String s; int[][] memo;
int enc(int x) { return x == 1 ? 1 : x < 10 ? 2 : x < 100 ? 3 : 4; }
public int getLengthOfOptimalCompression(String s, int k) {
this.s = s; this.n = s.length();
memo = new int[n + 1][k + 1];
for (int[] row : memo) Arrays.fill(row, -1);
return dp(0, k);
}
int dp(int i, int k) {
if (k < 0) return Integer.MAX_VALUE / 2;
if (i == n) return 0;
if (memo[i][k] != -1) return memo[i][k];
int best = dp(i + 1, k - 1);
int cnt = 0, del = 0;
for (int j = i; j < n; j++) {
if (s.charAt(j) == s.charAt(i)) cnt++; else del++;
if (del > k) break;
best = Math.min(best, enc(cnt) + dp(j + 1, k - del));
}
return memo[i][k] = best;
}
}int memo[101][101];
string ss;
int enc(int x) { return x == 1 ? 1 : x < 10 ? 2 : x < 100 ? 3 : 4; }
int dp(int i, int k) {
int n = ss.size();
if (k < 0) return 1e9;
if (i == n) return 0;
if (memo[i][k] != -1) return memo[i][k];
int best = dp(i + 1, k - 1);
int cnt = 0, del = 0;
for (int j = i; j < n; j++) {
if (ss[j] == ss[i]) cnt++; else del++;
if (del > k) break;
best = min(best, enc(cnt) + dp(j + 1, k - del));
}
return memo[i][k] = best;
}
int getLengthOfOptimalCompression(string s, int k) {
ss = s;
memset(memo, -1, sizeof memo);
return dp(0, k);
}Explanation
We may delete up to k characters to make the run-length encoded form of the string as short as possible (so aaab encodes as a3b1, length 4). The state that captures everything we need is dp(i, k): the best encoded length for the suffix starting at i with k deletions still available.
At each position there are two kinds of moves. One is simply to delete s[i], paying one deletion and recursing with dp(i+1, k-1).
The other is to keep a run of one chosen letter. We scan forward from i, counting how many characters match s[i] (cnt) and treating the non-matching ones as deletions. The cost of that run is enc(cnt) — the length of writing the letter plus its count digits — plus dp(j+1, k - deleted) for the rest. The helper enc returns 1 for a lone char, 2 up to 9 repeats, 3 up to 99, and so on.
Example: s = "aaabcccd", k = 2. Deleting the b and d leaves "aaaccc" which encodes as a3c3 — length 4, the minimum.
Because the same (i, k) pairs recur, memoization stores each one, giving the O(n² · k) running time.