Expand a Nested Repeat-Count Encoded String
Company: Abridge
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
You are given an encoded string `s`. The encoding rule is `k[text]`: the `text` inside the square brackets is repeated exactly `k` times, where `k` is a positive integer written in decimal. Encoded parts can be nested inside one another and can sit next to plain letters. Return the fully decoded string.
### Function Signature
```python
def decode(s: str) -> str:
```
### Rules
- `s` is always valid: brackets are balanced, every `[` is immediately preceded by its repeat count, every repeat count is immediately followed by `[`, and no pair of brackets is empty.
- Digits appear only as repeat counts, so the decoded string never contains digits.
- A repeat count can have more than one digit (for example `12[a]`) and has no leading zeros.
- Letters outside every pair of brackets are copied to the output unchanged.
### Constraints
- `1 <= len(s) <= 30`
- `s` contains only lowercase English letters, digits, `[` and `]`.
- Every repeat count `k` satisfies `1 <= k <= 300`.
- The decoded string has length at most 100,000.
### Examples
**Example 1**
```text
Input: s = "2[x3[yz]]w"
Output: "xyzyzyzxyzyzyzw"
```
The inner part `3[yz]` decodes to `"yzyzyz"`, so `x3[yz]` is `"xyzyzyz"`. That is repeated twice, and the trailing `w` is appended.
**Example 2**
```text
Input: s = "z10[q]"
Output: "zqqqqqqqqqq"
```
The output is `"z"` followed by ten `"q"` characters; the repeat count has two digits.
**Example 3**
```text
Input: s = "a2[b]c"
Output: "abbc"
```
Overview: From an Abridge online assessment: decode a string in which k[text] means the bracketed text repeated k times, with multi-digit counts, nested brackets and plain letters between encoded parts. It tests parsing nested structure correctly and building the expanded output efficiently.
You are given an encoded string `s`. The encoding rule is `k[text]`: the `text` inside the square brackets is repeated exactly `k` times, where `k` is a positive integer written in decimal. Encoded parts can be nested inside one another and can sit next to plain letters. Implement `decode(s)` so that it returns the fully decoded string.
### Rules
- `s` is always valid: brackets are balanced, every `[` is immediately preceded by its repeat count, every repeat count is immediately followed by `[`, and no pair of brackets is empty.
- Digits appear only as repeat counts, so the decoded string never contains digits.
- A repeat count can have more than one digit (for example `12[a]`) and has no leading zeros.
- Letters outside every pair of brackets are copied to the output unchanged.
### Constraints
- `1 <= len(s) <= 30`
- `s` contains only lowercase English letters, digits, `[` and `]`.
- Every repeat count `k` satisfies `1 <= k <= 300`.
- The decoded string has length at most 100,000.
No count or length in this problem can exceed 2^31 - 1, so 32-bit integers are sufficient in every language.
### Examples
**Example 1**
```text
Input: s = "2[x3[yz]]w"
Output: "xyzyzyzxyzyzyzw"
```
The inner part `3[yz]` decodes to `"yzyzyz"`, so `x3[yz]` is `"xyzyzyz"`. That is repeated twice, and the trailing `w` is appended.
**Example 2**
```text
Input: s = "z10[q]"
Output: "zqqqqqqqqqq"
```
The output is `"z"` followed by ten `"q"` characters; the repeat count has two digits.
Constraints
- 1 <= len(s) <= 30
- s contains only lowercase English letters, digits, '[' and ']'.
- Every repeat count k satisfies 1 <= k <= 300.
- The decoded string has length at most 100,000.
- s is always valid: brackets are balanced, every '[' is immediately preceded by its repeat count, every repeat count is immediately followed by '[', and no pair of brackets is empty.
- Digits appear only as repeat counts, and a repeat count has no leading zeros.
Examples
Input: ('a',)
Expected Output: 'a'
Explanation: Minimum length: a single plain letter is copied unchanged.
Input: ('1[a]',)
Expected Output: 'a'
Explanation: Smallest encoded form; k = 1 repeats the text exactly once.
Hints
- A repeat count can have more than one digit, so read the whole number before acting on the '[' that follows it.
- When a ']' closes a group, only the text decoded since its matching '[' is repeated; the text decoded before that '[' has to be kept so the repeated part can be attached to it.
- A letter that comes right after a ']' belongs to whatever encloses the group that just closed, either an outer group or the top-level string.