Decode a Run-Length Encoded String Where a Missing Count Means One

A string of lowercase letters has been compressed with run-length encoding: each run of one repeated letter is written as the letter followed by the length of the run in decimal, and a run of length one may be written as the letter alone. For example, a5b3c stands for aaaaabbbc. Implement the decoder that turns an encoded string back into the original.

The interviewer also expected you to write your own test cases for the decoder.

Function Signature

def decode_run_length(s: str) -> str:

Rules

• s is a sequence of tokens. A token is one lowercase letter, optionally followed by a count.
• A count is one or more decimal digits, never starts with 0, and is at least 1. A count can have several digits: a12 stands for twelve a characters.
• A token without a count stands for one copy of its letter; a token with count c stands for c copies.
• Decode the tokens from left to right and concatenate the results. Two consecutive tokens may use the same letter; each one is decoded on its own.
• The input is always a valid encoding under these rules.

Constraints

• 1 <= len(s) <= 10^4
• s contains only lowercase English letters and the digits 0 to 9, and its first character is a letter
• Every count satisfies 1 <= count <= 10^5
• The decoded string has length at most 10^5

Examples

Example 1

Input: s = "a5b3c"
Output: "aaaaabbbc"

Five a, three b, and one c written without a count.

Example 2

Input: s = "q10e"
Output: "qqqqqqqqqqe"

The count 10 has two digits, so the output has ten q followed by one e.

Example 3

Input: s = "ab2a"
Output: "abba"

The tokens are a, b2 and a; the letter a appears in two separate tokens.