String Compression II — Hard Problem & Solution

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…

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 <= 100
0 <= k <= s.length
s contains only lowercase English letters.

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] = 0 for every j.
Work i from n - 1 down to 0 and j from 0 to k.
Option A: if j > 0, delete s[i] for dp[i+1][j-1].
Option B: extend m from i rightwards, counting matches of s[i] in cnt and mismatches (deleted) in del; stop when del > j. Charge encLen(cnt) + dp[m+1][j-del].
encLen(c) is 1 for c = 1, 2 for c < 10, 3 for c < 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 k in 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue