Decode a Run-Length Encoded String Where a Missing Count Means One
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
Input: s = "a5b3c"
Output: "aaaaabbbc"
```
Five `a`, three `b`, and one `c` written without a count.
**Example 2**
```text
Input: s = "q10e"
Output: "qqqqqqqqqqe"
```
The count `10` has two digits, so the output has ten `q` followed by one `e`.
**Example 3**
```text
Input: s = "ab2a"
Output: "abba"
```
The tokens are `a`, `b2` and `a`; the letter `a` appears in two separate tokens.
Overview: Implement a decoder for run-length encoded strings in which each lowercase letter is followed by an optional repeat count, so that a5b3c becomes aaaaabbbc. It tests careful string parsing, multi-digit counts, letters written without a count, and writing your own test cases.
Read the full Apple Software Engineer interview experience this question came from
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 `decode_run_length(s)`, which decodes the encoded string `s` and returns the original string.
### 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 of its letter.
- 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`
Every count and length fits in a 32-bit signed integer; no value exceeds `2^31 - 1`.
### Examples
**Example 1**
```text
Input: s = "a5b3c"
Output: "aaaaabbbc"
```
Five `a`, three `b`, and one `c` written without a count.
**Example 2**
```text
Input: s = "q10e"
Output: "qqqqqqqqqqe"
```
The count `10` has two digits, so the output has ten `q` followed by one `e`.
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 has no leading zero and satisfies 1 <= count <= 10^5
- The decoded string has length at most 10^5
- s is always a valid encoding: a sequence of tokens, each one lowercase letter optionally followed by a count
Examples
Input: ('a',)
Expected Output: 'a'
Explanation: Minimum valid input: a single bare letter (len(s) = 1) decodes to one copy of itself.
Input: ('z7',)
Expected Output: 'zzzzzzz'
Explanation: Degenerate: one token with an explicit one-digit count; seven z, output length 7.
Hints
- A count can have more than one digit, as in q10e; make sure you have read the whole count before you expand its letter.
- A letter with no digits after it stands for exactly one copy, and that includes a letter at the very end of the string.
- Each token is decoded on its own, so two neighbouring tokens with the same letter need no special handling.