1531. String Compression II - Explanation

1. Dynamic Programming (Top-Down)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        cache = {}

        def count(i, k, prev, prev_cnt):
            if (i, k, prev, prev_cnt) in cache:
                return cache[(i, k, prev, prev_cnt)]
            if k < 0:
                return float("inf")
            if i == len(s):
                return 0

            if s[i] == prev:
                incr = 1 if prev_cnt in [1, 9, 99] else 0
                res = incr + count(i + 1, k, prev, prev_cnt + 1)
            else:
                res = min(
                    count(i + 1, k - 1, prev, prev_cnt),  # delete s[i]
                    1 + count(i + 1, k, s[i], 1)  # don't delete
                )

            cache[(i, k, prev, prev_cnt)] = res
            return res

        return count(0, k, "", 0)

Time & Space Complexity

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

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

2. Dynamic Programming (Top-Down Optimized)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        dp = {}

        def dfs(i, k):
            if n - i <= k:
                return 0
            if (i, k) in dp:
                return dp[(i, k)]

            res = 150
            if k > 0:
                res = dfs(i + 1, 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 > k:
                        break
                res = min(res, comp_len + dfs(j + 1, k - delCnt))
            dp[(i, k)] = res
            return res

        return dfs(0, k)

Time & Space 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.

3. Dynamic Programming (Bottom-Up)

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]

Time & Space 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.