1531. Incorrect

NOCHAR = 27

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        N = len(s)

        if N == k:
            return 0

        s = [ord(c) - ord('a') for c in s]

        def min_(old, cand):
            if old is None:
                return cand
            return min(old, cand)

        def encoding_len(num_chars: int) -> int:
            if num_chars <= 1:
                return num_chars
            return 1 + len(str(num_chars))

        @cache
        def dp(prefix_len: int, num_dels: int, last_char: int) -> Optional[Tuple[int, int]]:
            if prefix_len == 0:
                return None if last_char != NOCHAR else (0, 0)

            if last_char == NOCHAR:
                return None if prefix_len > num_dels else (0, 0)

            best = None
            if s[prefix_len - 1] == last_char:
                for c in range(27 + 1):
                    prev_best = dp(prefix_len - 1, num_dels, c)
                    if prev_best is None:
                        continue

                    if c == last_char:
                        new_len = prev_best[0] - encoding_len(prev_best[1]) + encoding_len(prev_best[1] + 1)
                        best = min_(best, (new_len, prev_best[1] + 1))
                        continue

                    best = min_(best, (prev_best[0] + 1, 1))

            if num_dels > 0:
                prev_best = dp(prefix_len - 1, num_dels - 1, last_char)
                if prev_best is not None:
                    best = min_(best, prev_best)

            return best

        for i in range(N + 1):
            print(i, 'a', dp(i, 1, 0), dp(i, 0, 0))
            print(i, 'b', dp(i, 1, 1), dp(i, 0, 1))
            print(i, 'N', dp(i, 1, NOCHAR), dp(i, 0, NOCHAR))
            print()

        ans = max(
            dp(N, k, c) for c in range(27 + 1) if dp(N, k, c) is not None
        )
        return ans[0]

#         # DP[prefix][num_dels][last_char] = (encoded len, num_last_char)
#         dp = [[[None] * 27 for _ in range(k + 1)] for _ in range(len(s) + 1)]
#         dp[0][0][NOCHAR] = (0, 0)

#         for prefix_len in range(1, N + 1):
#             for dels_used in range(k):
#                 pass

#         ans = max(
#             dp[N][k][c] for c in range(27 + 1) if dp[N][k][c] is not None
#         )
#         return ans[0]