Character at a Position in a Run-Length Encoded String Without Decoding

A sequence of characters has been stored with run-length encoding: each maximal run of one repeated character is written as the character followed by the run length. For example, the sequence B, A, A, E, E, E, C is stored as "B1A2E3C1".

Implement a lookup that, working from the encoded data, returns the character at position p of the original (decoded) sequence. The runs can be very long, so decoding the whole sequence is not an option. The console version answers a batch of positions in one call.

Function Signature

def char_at_positions(encoded: str, positions: list[int]) -> list[str]:

Rules

• encoded is a concatenation of runs. Each run is one uppercase English letter followed by its length written in decimal with no leading zeros.
• Positions are 0-indexed into the decoded sequence.
• Return one single-character string per query, in the same order as positions.

Constraints

• 1 <= number of runs <= 10^5
• Each run length is an integer in [1, 10^9].
• The decoded length (the sum of all run lengths) is at most 10^14, which is below 2^53.
• 1 <= len(positions) <= 10^5
• 0 <= positions[j] < decoded length.

Examples

Example 1

• Input: encoded = "B1A2E3C1", positions = [0, 1, 2, 3, 5, 6]
• Output: ["B", "A", "A", "E", "E", "C"]
• Explanation: The decoded sequence is B A A E E E C, with positions 0 through 6.

Example 2

• Input: encoded = "X1000000000Y1Z25", positions = [999999999, 1000000000, 1000000001, 1000000025]
• Output: ["X", "Y", "Z", "Z"]
• Explanation: Positions 0 to 999999999 hold X, position 1000000000 holds Y, and positions 1000000001 to 1000000025 hold Z.