Problem statement

https://binarysearch.com/problems/Lossy-Run-Length-Encoding/

Solution

Let us keep for each prefix and each suffix the following information: (last symbol, count of it, total length of encoded string). Then we can evaluate all these data in O(n). We check if the next symbol is equal to last one and if it is the same, we check if we have edge case, when length goes from 1 -> 2, 9 -> 10, 99 -> 100, in this case encoding length will increase by one.

After we calculate all this data, we can use it to evaluate what run-length encoding of two parts will be. We need to check if the symbol in the middle is the same and if it is, correct length.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s, k):
        n = len(s)
        edges = set([1, 9, 99, 999, 9999, 99999, 999999])

        def f(s):
            arr = [("!", 1, 0)]  #last symb, count of it, total length
            for x in s:
                symb, cnt, ln = arr[-1]
                if x != symb:
                    arr += [(x, 1, ln + 1)]
                else:
                    addon = cnt in edges
                    arr += [(x, cnt + 1, ln + addon)]
            return arr

        lft = f(s)
        rgh = f(s[::-1])[::-1]
        ans = float("inf")

        for i in range(n - k + 1):
            L, R = lft[i], rgh[i + k]
            if L[0] != R[0]:
                ans = min(ans, L[2] + R[2])
            else:
                fix = - len(str(L[1])) - len(str(R[1])) + len(str(L[1] + R[1])) - 1
                if L[1] == 1: fix += 1
                if R[1] == 1: fix += 1
                ans = min(ans, L[2] + R[2] + fix)
        
        return ans