String Compression II — LeetCode 1531 Python Solution

The problem

Run-length encoding 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".

Example

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.

Python solution

from functools import lru_cache

def getLengthOfOptimalCompression(s: str, k: int) -> int:
    n = len(s)

    @lru_cache(None)
    def dp(i: int, last: str, run: int, k_left: int) -> int:
        if k_left < 0:
            return 10**9
        if i == n:
            return 0

        # Option 1: delete s[i]
        best = dp(i + 1, last, run, k_left - 1)

        # Option 2: keep s[i]
        if s[i] == last:
            inc = 1 if run in (1, 9, 99) else 0
            best = min(best, inc + dp(i + 1, last, run + 1, k_left))
        else:
            best = min(best, 1 + dp(i + 1, s[i], 1, k_left))

        return best

    return dp(0, '#', 0, k)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1531. String Compression II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems