String Compression II

Hard
1035.

String Compression II

String Compression II is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var getLengthOfOptimalCompression = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for String Compression II

  1. 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.

  2. 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.

  3. Hint 3

    State: dp[i][j] = the best encoding of s[i..] with j deletions 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

  1. Set dp[n][j] = 0 for every j.
  2. Work i from n - 1 down to 0 and j from 0 to k.
  3. Option A: if j > 0, delete s[i] for dp[i+1][j-1].
  4. 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].
  5. encLen(c) is 1 for c = 1, 2 for c < 10, 3 for c < 100, else 4.
  6. 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]

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