String Compression II

Hard

#1411Time: O(n^2 * k). The number of states is `n * k`. For each state `(i, k)`, we perform a loop that runs at most `n` times to decide the end of the current run.Space: O(n * k), where n is the string length and k is the max deletions. This is dominated by the size of the memoization table. The recursion stack depth adds O(n).1 company

Patterns

Dynamic Programming

Data structures

String

Companies

Toptal

Prompt

Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". Thus the compressed string becomes "a2bc3".

Notice that in this problem, we are not adding '1' after single characters.

Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length.

Find the minimum length of the run-length encoded version of s after deleting at most k characters.

Example 1:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

Example 2:

Input: s = "aabbaa", k = 2
Output: 2
Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.

Example 3:

Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.

Constraints:

1 <= s.length <= 100
0 <= k <= s.length
s contains only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

The brute-force recursion is slow due to recomputing the same subproblems. We can significantly optimize it by storing the results of each subproblem (i, k) in a cache or memoization table. This ensures that each subproblem is solved only once. This technique is known as memoization or top-down dynamic programming and is efficient enough to solve this problem within the given constraints.

Algorithm

Initialize a 2D array memo[n][k+1] with a sentinel value (e.g., -1) to store computed results.
Define a recursive function solve(i, k) that returns the minimum length for s[i:] with k deletions.
Base Cases:
- If k < 0, return a large value (infinity).
- If i >= n or n - i <= k, return 0.
Memoization Check: If memo[i][k] is not -1, return it.
Recursive Step:
- Calculate the result res by considering two choices:
  1. Delete s[i]: res = solve(i + 1, k - 1).
  2. Keep s[i]: Iterate j from i to n-1. In s[i...j], count s[i]'s (count) and others (deleted). If deleted <= k, update res = min(res, getLen(count) + solve(j + 1, k - deleted)).
Store the final res in memo[i][k] before returning.
The main function calls solve(0, k).

Walkthrough

We use a 2D array, memo[n][k+1], to store the results of our recursive function solve(i, k). memo[i][k] will hold the minimum compressed length for the suffix s[i:] with k deletions. The logic of the solve function remains the same as the brute-force version. However, before any computation, we check if memo[i][k] has already been computed. If it has, we return the stored value immediately. If not, we compute the result as before, and just before returning, we store it in memo[i][k]. This simple addition prunes the recursion tree drastically, avoiding redundant computations. The state transition is: memo[i][k] = min(solve(i+1, k-1), min_{j=i..n-1} (getLen(count) + solve(j+1, k-deleted))) where count and deleted are for the substring s[i..j] to form a run of s[i].

1class Solution {2    int[][] memo;3    String s;4    int n;5 6    // Helper to calculate the length of an encoded run7    private int getLen(int count) {8        if (count == 1) return 1;9        if (count < 10) return 2;10        if (count < 100) return 3;11        return 4;12    }13 14    private int solve(int i, int k) {15        // Base case: invalid number of deletions16        if (k < 0) {17            return 101; // Using a value larger than max possible length18        }19        // Base case: end of string or can delete all remaining chars20        if (i >= n || n - i <= k) {21            return 0;22        }23 24        // Return memoized result if available25        if (memo[i][k] != -1) {26            return memo[i][k];27        }28 29        // Option 1: Delete the character s[i]30        int res = solve(i + 1, k - 1);31 32        // Option 2: Keep s[i] and form a run of this character.33        // We iterate through all possible end points 'j' for this run.34        int deletedCount = 0;35        int keepCount = 0;36        for (int j = i; j < n; j++) {37            if (s.charAt(j) == s.charAt(i)) {38                keepCount++;39            } else {40                deletedCount++;41            }42 43            // If we have enough deletions available for this run44            if (deletedCount <= k) {45                // Calculate the length of this choice46                int currentLen = getLen(keepCount) + solve(j + 1, k - deletedCount);47                res = Math.min(res, currentLen);48            } else {49                // If we need more deletions than available, we can't extend this run further50                break;51            }52        }53 54        // Memoize and return the result55        return memo[i][k] = res;56    }57 58    public int getLengthOfOptimalCompression(String s, int k) {59        this.s = s;60        this.n = s.length();61        this.memo = new int[n][k + 1];62        for (int row = 0; row < n; row++) {63            java.util.Arrays.fill(memo[row], -1);64        }65        return solve(0, k);66    }67}

Complexity

Time

O(n^2 * k). The number of states is `n * k`. For each state `(i, k)`, we perform a loop that runs at most `n` times to decide the end of the current run.

Space

O(n * k), where n is the string length and k is the max deletions. This is dominated by the size of the memoization table. The recursion stack depth adds O(n).

Trade-offs

Pros

Finds the optimal solution efficiently by avoiding redundant calculations.
Passes the time limits for the given constraints.
It's a standard and robust way to solve this type of combinatorial optimization problem.

Cons

The space complexity of O(n*k) might be an issue for problems with much larger constraints, but it is acceptable here.

A straightforward approach is to explore every possible decision at each character: either delete it or keep it. This can be modeled with a recursive function. If we decide to keep a character, it starts a new run, and we must then decide which subsequent characters to keep or delete to extend this run. This recursive exploration without any optimization forms the brute-force solution.

Algorithm

Define a recursive function solve(i, k) that computes the minimum length for the suffix s[i:] with k deletions.
Base Case 1: If k < 0, it's an invalid path, so return a large value (infinity).
Base Case 2: If i is out of bounds (i >= n) or the remaining string length n-i is less than or equal to k, we can delete all remaining characters, so the cost is 0.
Recursive Step:
- Initialize a result variable res to infinity.
- Choice 1 (Delete s[i]): If k > 0, the result for this choice is solve(i + 1, k - 1). Update res with this value.
- Choice 2 (Keep s[i]): Start a new run with s[i]. Iterate through all possible end positions j for this run (from i to n-1). For each j, calculate the number of characters to delete (deleted) in s[i...j] to make it a solid run of s[i]. If deleted <= k, this is a valid move. The cost is getLen(count) + solve(j + 1, k - deleted), where count is the number of s[i]'s in s[i...j]. Update res with the minimum.
The function returns the minimum res found.
The initial call is solve(0, k).

Walkthrough

We define a recursive function, say solve(index, k_left), which calculates the minimum compressed length for the suffix of the string starting at index with k_left deletions remaining. At each index, we have two main choices:

Delete s[index]: If we have deletions left (k_left > 0), we can delete the current character. The problem then reduces to solve(index + 1, k_left - 1).
Keep s[index]: We start a new run with the character s[index]. We then iterate through all possible end points j for this run (from index to the end of the string). For each j, we would form a run of s[index] using characters from the substring s[index...j]. This requires deleting all characters in this substring that are not equal to s[index]. If the number of required deletions does not exceed k_left, this is a valid choice. The length would be the length of the compressed run plus the result of the recursive call on the rest of the string: getLen(run_count) + solve(j + 1, k_left - deletions_needed). The function returns the minimum value found among all these choices. This approach is correct but highly inefficient because it recalculates solutions for the same subproblems (index, k_left) repeatedly.

Complexity

Time

Exponential, e.g., O(n * 2^n). The function branches multiple times at each step, and without memoization, the same subproblems are solved over and over, leading to an exponential number of calls.

Space

O(n), where n is the length of the string. This is for the recursion stack depth.

Trade-offs

Pros

Conceptually simple and directly follows the problem's decision structure.

Cons

Extremely inefficient due to massive re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error for most test cases beyond trivial ones.

Solutions

Solution

1class Solution {2public3  int getLengthOfOptimalCompression(String s, int k) {

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem