Lazy Run-Length Decoding - Google Top Interview Questions

                        Solution in C++ :

class RunLengthDecoder {
    public:
    map<char, vector<pair<int, int>>> charToRanges;
    vector<pair<int, int>> ranges;
    vector<char> chars;
    RunLengthDecoder(string s) {
        int curr = 0;
        int amt = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                charToRanges[s[i]].emplace_back(amt, amt + curr);
                ranges.emplace_back(amt, amt + curr);
                chars.push_back(s[i]);
                amt += curr;
                curr = 0;
            } else {
                curr *= 10;
                curr += s[i] - '0';
            }
        }
        assert(curr == 0);
    }

    string value(int i) {
        auto it = upper_bound(ranges.begin(), ranges.end(), make_pair(i + 1, (int)-1e9));
        it--;
        int idx = it - ranges.begin();
        return string(1, chars[idx]);
    }

    string valueInRange(string c, int i, int j) {
        for (char ch = c[0]; ch <= 'z'; ch++) {
            auto it = upper_bound(charToRanges[ch].begin(), charToRanges[ch].end(),
                                  make_pair(j, (int)-1e9));
            if (it != charToRanges[ch].begin()) it--;
            if (it == charToRanges[ch].end()) continue;
            pair<int, int> key = *it;
            if (key.second <= i || key.first >= j) continue;
            return string(1, ch);
        }
        return "?";
    }
};
                    

                        Solution in Java :

import java.util.*;

class RunLengthDecoder {
    private StringBuilder sb = new StringBuilder();
    private List<Integer> begins = new ArrayList<>();

    public RunLengthDecoder(String s) {
        for (int i = 0, end = 0; i != s.length(); i++) {
            int j = i;
            while (Character.isDigit(s.charAt(j + 1))) j++;
            begins.add(end);
            int len = Integer.parseInt(s.substring(i, j + 1));
            if (len != 0) {
                end += Integer.parseInt(s.substring(i, j + 1));
                sb.append(s.charAt(j + 1));
            }
            i = j + 1;
        }
    }

    public String value(int i) {
        int idx = Collections.binarySearch(begins, i);
        if (idx < 0)
            idx = -2 - idx;
        return sb.substring(idx, idx + 1);
    }

    public String valueInRange(String c, int i, int j) {
        int idx = Collections.binarySearch(begins, i);
        if (idx < 0)
            idx = -2 - idx;
        final char ch = c.charAt(0);
        for (int round = 0; idx != sb.length() && round != 26; round++, idx++) {
            if (begins.get(idx) >= j)
                break;
            if (sb.charAt(idx) >= ch)
                return Character.toString(sb.charAt(idx));
        }
        return "?";
    }
}
                    

                        Solution in Python : 
                            
class RunLengthDecoder:
    def __init__(self, s):
        self.chars = []
        self.indexes = [0]

        char_count = 0
        for char in s:
            if not char.isdigit():
                self.chars.append(char)
                self.indexes.append(self.indexes[-1] + char_count)
                char_count = 0
            else:
                char_count = char_count * 10 + int(char)

        self.next_indexes = [[self.indexes[-1]] * 26 for _ in range(len(s) + 1)]

        for i in range(len(self.chars) - 1, -1, -1):
            self.next_indexes[i] = self.next_indexes[i + 1][:]
            char_num = ord(self.chars[i]) - ord("a")
            self.next_indexes[i][char_num] = self.indexes[i]

    def value(self, i):
        char_index = max(0, bisect_right(self.indexes, i) - 1)
        return self.chars[char_index]

    def valueInRange(self, c, i, j):
        char_index = max(0, bisect_right(self.indexes, i) - 1)
        next_indexes = self.next_indexes[char_index]
        char_num = ord(c) - ord("a")
        for num in range(char_num, 26):
            if next_indexes[num] < j:
                return chr(num + ord("a"))
        return "?"