Problem statement

https://binarysearch.com/problems/Lazy-Run-Length-Decoding/

Solution

First, transform encoded string to pairs (value, letter), then find cumulative sums. Then for value we can use binary search in places. For valueInRange we can use binary search by indexes: for each value use value function.

Complexity

It is O(n) for time. For value it is O(log n). For valueInRange it is O(log n * log M), where M is the maximum range we can have.

Code

class RunLengthDecoder:
    def __init__(self, s):
        B = ["".join(x) for _, x in groupby(s, key=lambda x: x.isdigit())]
        pairs = [[B[2*i+1], int(B[2*i])] for i in range(len(B)//2)]
        self.places = [0] + list(accumulate(y for _, y in pairs))
        self.letters = [x for x, _ in pairs]

    def value(self, i):
        idx = bisect.bisect(self.places, i)
        return self.letters[idx - 1]
        
    def valueInRange(self, c, i, j):
        beg, end = i - 1, j
        while beg + 1 < end:
            mid = (beg + end)//2
            if self.value(mid) < c:
                beg = mid
            else:
                end = mid
        
        return self.value(end) if end < j else "?"

Remark

Notice, that alternative way for valueInRange is to keep places for each letter, then complexity will be O(26 * log n), which works similar in this problem, but for other constraints can be different.