String Compression II

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.

• 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).

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

class Solution {
    int[][] memo;
    String s;
    int n;

    // Helper to calculate the length of an encoded run
    private int getLen(int count) {
        if (count == 1) return 1;
        if (count < 10) return 2;
        if (count < 100) return 3;
        return 4;
    }

    private int solve(int i, int k) {
        // Base case: invalid number of deletions
        if (k < 0) {
            return 101; // Using a value larger than max possible length
        }
        // Base case: end of string or can delete all remaining chars
        if (i >= n || n - i <= k) {
            return 0;
        }

        // Return memoized result if available
        if (memo[i][k] != -1) {
            return memo[i][k];
        }

        // Option 1: Delete the character s[i]
        int res = solve(i + 1, k - 1);

        // Option 2: Keep s[i] and form a run of this character.
        // We iterate through all possible end points 'j' for this run.
        int deletedCount = 0;
        int keepCount = 0;
        for (int j = i; j < n; j++) {
            if (s.charAt(j) == s.charAt(i)) {
                keepCount++;
            } else {
                deletedCount++;
            }

            // If we have enough deletions available for this run
            if (deletedCount <= k) {
                // Calculate the length of this choice
                int currentLen = getLen(keepCount) + solve(j + 1, k - deletedCount);
                res = Math.min(res, currentLen);
            } else {
                // If we need more deletions than available, we can't extend this run further
                break;
            }
        }

        // Memoize and return the result
        return memo[i][k] = res;
    }

    public int getLengthOfOptimalCompression(String s, int k) {
        this.s = s;
        this.n = s.length();
        this.memo = new int[n][k + 1];
        for (int row = 0; row < n; row++) {
            java.util.Arrays.fill(memo[row], -1);
        }
        return solve(0, k);
    }
}