Kth Letter of Runs
Medium · binary search
A long message is stored in compressed form. You are given letters, a string, and counts, a list of the same length. The full message is letters[0] repeated counts[0] times, followed by letters[1] repeated counts[1] times, and so on. Neighbouring runs may use the same letter. The counts can be as large as 10^9, so the full message can be far too long to build.
You are also given queries, a list of positions in the full message (counting from 0). For each query, find the letter at that position.
Return a string whose i-th character is the answer to queries[i], in the same order. The queries are in no particular order, and the same position may appear more than once. Every query is a valid position.
Examples
Example 1
Input: letters = "abc", counts = [2, 3, 1], queries = [0, 2, 5]
Output: "abc"
The message is aabbbc. Position 0 is a, position 2 is the first b, position 5 is c.
Example 2
Input: letters = "xy", counts = [1000000000, 1000000000], queries = [999999999, 1000000000, 1999999999]
Output: "xyy"
The message has 2 * 10^9 characters. The first 10^9 are x, the rest are y.
Example 3
Input: letters = "q", counts = [4], queries = [3, 0, 3]
Output: "qqq"
Constraints
- 1 <= len(letters) == len(counts) <= 10^5
- letters contains only lower-case English letters
- 1 <= counts[i] <= 10^9
- 1 <= len(queries) <= 10^5
- 0 <= queries[i] < sum(counts)