1
class Solution:
2
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
3
        # We define f(i, curr_run_ch, run_length, nb_dels_remain) to return
4
        # the minimum, additional, number of characters it will cost to run-length
5
        # compress the substring s[i..n-1].
6
        # `curr_run_ch` is the character we have in the current "run", or the same
7
        # contiguous block of characters.
8
        # `run_length` is the length of the current "run", or the length of the
9
        # contiguous block of identical characters.
10
        #     e.g. if we just encoded "aaaaa", `curr_run_ch` is "a" and `run_length` = 5
11
        # `nb_dels_remain` is the number of delete operations we have available to us,
12
        # should we choose to use them
13
        memo = {}
14

15
        def f(i, curr_run_ch, run_length, nb_dels_remain):
16
            if i == len(s):
17
                return 0
18

19
            key = (i, curr_run_ch, run_length, nb_dels_remain)
20
            if key in memo:
21
                return memo[key]
22

23
            # At character i, we have two possible options, we could choose to either
24
            # delete this character or keep this character. Each choice we make will
25
            # incurr some additional run-length encoding length for s[i..n-1]. We return
26
            # the minimum of the two.
27

28
            # Delete s[i]
29
            del_ch_cost = float("inf")
30
            if nb_dels_remain > 0:
31
                # Deleting s[i] means the latest character we kept stays the same AND
32
                # the current run-length of characters stays the same as well
33
                del_ch_cost = f(i + 1, curr_run_ch, run_length, nb_dels_remain - 1)
34

35
            # Keep s[i]
36
            keep_ch_cost = 0
37
            if s[i] == curr_run_ch:
38
                # The new character at s[i] we are about to encode is the same as the character in the
39
                # current "run", we could choose to include it into the current run of course.
40
                # Be careful that if we started with run-length of 1, 9, 99, 999 and etc, encoding another
41
                # character same as `curr_run_ch`  into the same "run" will require an extra digit.
42
                # e.g. 'a' => '2a' '9a' => '10a', '99a' => '100a'
43
                extra_digit_cost = 0
44
                if run_length == 1 or len(str(run_length + 1)) > len(str(run_length)):
45
                    extra_digit_cost = 1
46
                keep_ch_cost = extra_digit_cost + f(
47
                    i + 1, curr_run_ch, run_length + 1, nb_dels_remain
48
                )
49
            else:
50
                # s[i] != curr_run_ch, we are going to need to run-length encode at least
51
                # one instance of s[i] which would cost 1, plus whatever the cost to encode
52
                # the rest. Of course that also means the current "run" will "reset" and start anew with
53
                # a single character s[i]
54
                keep_ch_cost = 1 + f(i + 1, s[i], 1, nb_dels_remain)
55

56
            memo[key] = min(keep_ch_cost, del_ch_cost)
57
            return memo[key]
58

59
        return f(0, "", 0, k)