String Compression II — Solution in Python, Java & C++
String Compression II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
String Compression II is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Run-length encoding rewrites a string by replacing each maximal run of one repeated character with that character followed by its count — the count is omitted when the run has length 1. So "aabccc" encodes as "a2bc3", which is 5 characters long.
Delete at most k characters from s and return the minimum possible length of the run-length encoding of what remains.
Example 1
Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Delete `b` and `d` to leave `aaaccc`, encoded as `a3c3`.
Example 2
Input: s = "aabbaa", k = 2
Output: 2
Explanation: Delete both `b`s to leave `aaaa`, encoded as `a4`.
Example 3
Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Eleven `a`s encode as `a11` — the count itself costs two characters.
Constraints
1 <= s.length <= 1000 <= k <= s.lengths contains only lowercase English letters.
Hints for String Compression II
Hint 1
The cost of a run is not its length — it is 1, 2, 3 or 4 characters depending on whether the count is 1, under 10, under 100, or more.
Hint 2
Think of building the answer left to right, deciding for each position either to delete it or to start a new run there.
Hint 3
State:
dp[i][j]= the best encoding ofs[i..]withjdeletions still available.
How to solve String Compression II
Define dp[i][j] as the minimum encoded length of the suffix starting at i using at most j deletions. From position i you either delete s[i], or you commit to a run of s[i]: scan right, keeping every character equal to s[i] and deleting every other one, and at each point charge the run's encoded cost plus the best answer for the rest.
Approach
- Set
dp[n][j] = 0for everyj. - Work
ifromn - 1down to 0 andjfrom 0 tok. - Option A: if
j > 0, deletes[i]fordp[i+1][j-1]. - Option B: extend
mfromirightwards, counting matches ofs[i]incntand mismatches (deleted) indel; stop whendel > j. ChargeencLen(cnt) + dp[m+1][j-del]. encLen(c)is 1 forc = 1, 2 forc < 10, 3 forc < 100, else 4.- Return
dp[0][k].
Why it works
The whole difficulty is that the cost of a run is not linear in its length — merging two runs of a by deleting a b between them may save nothing, or may save two characters if it pushes the count past 9. That rules out any greedy rule, and it is why the state has to fix the start of a run and enumerate where it ends: only then is the run's count, and therefore its cost, known. Deleting every non-matching character inside the scanned window is optimal for that choice, since a survivor would split the run and cost strictly more.
Complexity
- Time —
O(n² · k) - Space —
O(n · k)
Pitfalls
- A run of length 1 encodes as a single character — no count is written.
- The digit-count thresholds (10 and 100) are what make greedy approaches fail.
- Deletions are capped at
kin total across the whole string, not per run.
Reference solution
Python
def getLengthOfOptimalCompression(s: str, k: int) -> int:
n = len(s)
INF = 10**9
def enc(cnt: int) -> int:
if cnt == 1:
return 1
if cnt < 10:
return 2
if cnt < 100:
return 3
return 4
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(k + 1):
best = dp[i + 1][j - 1] if j > 0 else INF
cnt = 0
dele = 0
for m in range(i, n):
if s[m] == s[i]:
cnt += 1
else:
dele += 1
if dele > j:
break
best = min(best, enc(cnt) + dp[m + 1][j - dele])
dp[i][j] = best
return dp[0][k]Java
public static int getLengthOfOptimalCompression(String s, int k) {
int n = s.length();
final int INF = 1000000000;
int[][] dp = new int[n + 1][k + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= k; j++) {
int best = j > 0 ? dp[i + 1][j - 1] : INF;
int cnt = 0, del = 0;
for (int m = i; m < n; m++) {
if (s.charAt(m) == s.charAt(i)) cnt++;
else {
del++;
if (del > j) break;
}
int len = cnt == 1 ? 1 : cnt < 10 ? 2 : cnt < 100 ? 3 : 4;
best = Math.min(best, len + dp[m + 1][j - del]);
}
dp[i][j] = best;
}
}
return dp[0][k];
}C++
int getLengthOfOptimalCompression(string s, int k) {
int n = (int) s.size();
const int INF = 1000000000;
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= k; j++) {
int best = j > 0 ? dp[i + 1][j - 1] : INF;
int cnt = 0, del = 0;
for (int m = i; m < n; m++) {
if (s[m] == s[i]) cnt++;
else {
del++;
if (del > j) break;
}
int len = cnt == 1 ? 1 : cnt < 10 ? 2 : cnt < 100 ? 3 : 4;
best = min(best, len + dp[m + 1][j - del]);
}
dp[i][j] = best;
}
}
return dp[0][k];
}JavaScript
var getLengthOfOptimalCompression = function(s, k) {
var n = s.length, INF = 1000000000, i, j;
var enc = function(cnt) {
if (cnt === 1) return 1;
if (cnt < 10) return 2;
if (cnt < 100) return 3;
return 4;
};
var dp = [];
for (i = 0; i <= n; i++) {
var row = [];
for (j = 0; j <= k; j++) row.push(0);
dp.push(row);
}
for (i = n - 1; i >= 0; i--) {
for (j = 0; j <= k; j++) {
var best = j > 0 ? dp[i + 1][j - 1] : INF;
var cnt = 0, del = 0;
for (var m = i; m < n; m++) {
if (s.charAt(m) === s.charAt(i)) cnt++;
else { del++; if (del > j) break; }
var cand = enc(cnt) + dp[m + 1][j - del];
if (cand < best) best = cand;
}
dp[i][j] = best;
}
}
return dp[0][k];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming