# String Compression II
**Difficulty:** HARD
[External](https://leetcode.com/problems/string-compression-ii)
Canonical: https://scaleengineer.com/dsa/problems/string-compression-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Toptal](https://scaleengineer.com/companies/toptal)
---
## Problem
[Run-length encoding](http://en.wikipedia.org/wiki/Run-length%5Fencoding) 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
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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:
1.  **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)`.
2.  **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.
### 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)`.

## Dynamic Programming with Memoization
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.
**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).
**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.
### Explanation
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]`.
```java
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);
    }
}
```
### 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)`.

# Solutions
### Java

```java
class Solution {
public
  int getLengthOfOptimalCompression(String s, int k) {
```