String Compression II

How it works

We convert the optimized top-down solution to bottom-up form. We process positions from right to left, computing for each position and deletion budget the minimum encoded length. This iterative approach fills the DP table systematically and avoids recursion overhead.

Steps

1. Create a 2D DP array dp[n+1][k+1] initialized to a large value (e.g., 150), with dp[n][*] = 0 as base cases.
2. Iterate i from n-1 down to 0, and for each rem_k from 0 to k.
3. Option 1: if rem_k > 0, set dp[i][rem_k] = dp[i+1][rem_k-1] (delete current character).
4. Option 2: scan forward from i, counting frequency of s[i] and deletions of other characters. Track compressed length (starts at 1, increases at thresholds 1, 9, 99). Update dp[i][rem_k] = min(dp[i][rem_k], comp_len + dp[j+1][rem_k - delCnt]).
5. Stop scanning when delCnt > rem_k.
6. Return dp[0][k].

Complexity

• Time complexity: O(n ^ 2 * k)
• Space complexity: O(n * k)

Where n is the length of the string s and k is the maximum number of characters that can be deleted from the string.

Things to watch for

Miscounting Run-Length Encoding Length

The encoded length does not increase linearly with count. It is 1 for a single character (e.g., "a"), 2 for counts 2-9 (e.g., "a5"), 3 for counts 10-99 (e.g., "a12"), and 4 for count 100 (e.g., "a100"). The length only increases at thresholds 1, 9, and 99. Missing these thresholds leads to incorrect length calculations.

Not Considering All Deletion Strategies

A greedy approach of only deleting characters that break runs fails. Sometimes deleting characters within a run or deleting characters to merge two separate runs of the same character produces a shorter encoding. The DP must explore both keeping and deleting each character.

Incorrect State Representation

Tracking only position and remaining deletions is insufficient for the naive approach. You also need to track the previous character and its count to properly compute the contribution to encoded length. The optimized approach avoids this by scanning forward to form complete runs.

Integer Overflow with Infinity Values

Using INT_MAX or Integer.MAX_VALUE as infinity and then adding to it causes overflow. Either use a smaller sentinel value (like 150, which exceeds the maximum possible answer) or check for infinity before performing arithmetic operations.

Off-by-One Errors in Loop Termination

When scanning forward to extend a run, ensure you correctly handle the boundary when j reaches n. The base case when all remaining characters can be deleted (n - i <= k) should return 0. Failing to check bounds before accessing s[j] causes runtime errors.

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[150] * (k + 1) for _ in range(n)]
        dp.append([0] * (k + 1))

        for i in range(n - 1, -1, -1):
            for rem_k in range(k + 1):
                if rem_k > 0:
                    dp[i][rem_k] = dp[i + 1][rem_k - 1]

                freq = delCnt = 0
                comp_len = 1
                for j in range(i, n):
                    if s[i] == s[j]:
                        if freq in [1, 9, 99]:
                            comp_len += 1
                        freq += 1
                    else:
                        delCnt += 1
                        if delCnt > rem_k:
                            break
                    dp[i][rem_k] = min(dp[i][rem_k], comp_len + dp[j + 1][rem_k - delCnt])

        return dp[0][k]

class Solution {
public:
    int getLengthOfOptimalCompression(string s, int k) {
        int n = s.size();
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 150));

        for (int remK = 0; remK <= k; remK++) {
            dp[n][remK] = 0;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int remK = 0; remK <= k; remK++) {
                if (remK > 0) {
                    dp[i][remK] = dp[i + 1][remK - 1];
                }

                int freq = 0, delCnt = 0, compLen = 1;
                for (int j = i; j < n; j++) {
                    if (s[i] == s[j]) {
                        if (freq == 1 || freq == 9 || freq == 99) {
                            compLen++;
                        }
                        freq++;
                    } else {
                        delCnt++;
                        if (delCnt > remK) break;
                    }
                    dp[i][remK] = min(dp[i][remK], compLen + dp[j + 1][remK - delCnt]);
                }
            }
        }

        return dp[0][k];
    }
};