String Compression II Python Solution

lcpy gen -n 1531   # by problem number
lcpy gen -s string_compression_ii   # by problem name

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.

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)