> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# String Compression II Python Solution

> Tested Python solution for LeetCode 1531 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 1531, [Hard](/catalog/hard). Topics: [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/string-compression-ii/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1531   # by problem number
lcpy gen -s string_compression_ii   # by problem name
```

## Problem

\<a href="[http://en.wikipedia.org/wiki/Run-length\_encoding">Run-length](http://en.wikipedia.org/wiki/Run-length_encoding">Run-length) encoding\</a> 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 \<code>"aabccc"\</code> we replace \<code>"aa"\</code> by \<code>"a2"\</code> and replace \<code>"ccc"\</code> by \<code>"c3"\</code>. Thus the compressed string becomes \<code>"a2bc3"\</code>.

Notice that in this problem, we are not adding \<code>'1'\</code> after single characters.

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

Find the \<em>minimum length of the run-length encoded version of \</em>\<code>s\</code>\<em> after deleting at most \</em>\<code>k\</code>\<em> characters\</em>.

### Examples

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

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

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/string_compression_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/string_compression_ii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from functools import cache


class Solution:
    # Time: O(n^2 * k)
    # Space: O(n^2 * k)
    def get_length_of_optimal_compression(self, s: str, k: int) -> int:
        n = len(s)

        @cache
        def dp(i: int, remaining: int) -> int:
            if remaining < 0:
                return n + 1
            if i >= n or n - i <= remaining:
                return 0
            best = dp(i + 1, remaining - 1)
            count = 0
            for j in range(i, n):
                if s[j] == s[i]:
                    count += 1
                    cost = 1 if count == 1 else 1 + len(str(count))
                    deleted = j - i + 1 - count
                    best = min(best, cost + dp(j + 1, remaining - deleted))
            return best

        return dp(0, k)
```

## Complexity

| Time | Space |
| - | - |
| O(n^2 \* k) | O(n^2 \* k) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.