Expand Repeat Codes
MediumStack
Problem
A compressed text format writes k[body] to mean body repeated k times. Bodies can contain letters and further codes, so codes nest: 3[x2[yz]] is xyzyz three times.
Given a valid encoded string s, return the fully expanded text. Digits only ever appear as repeat counts directly before a [, and k is a positive integer that may have several digits.
Example 1
- Input:
- s = "2[ab]c"
- Output:
- "ababc"
Example 2
- Input:
- s = "3[x2[yz]]"
- Output:
- "xyzyzxyzyzxyzyz"
The inner 2[yz] becomes yzyz, so the body is xyzyz, repeated 3 times.
Constraints
- 1 ≤ s.length ≤ 100
- 1 ≤ k ≤ 300
- The expanded text has at most 10^5 characters
- Brackets are balanced and every '[' is preceded by a count
Hint
Show the first hint
When you reach ']', which '[' does it close, and what text was being built before that '['?
Walkthrough
How to approach it
01Clarify before coding
- Can k have several digits? Yes, e.g. "10[a]"; accumulate digits.
- Can letters appear outside any brackets? Yes, before, between and after codes.
- How large can the output be? Up to 10^5 characters, so build it efficiently.
02Brute force
Find an innermost code k[letters] (one with no '[' inside), replace it by its expansion, and repeat until no brackets remain.
Cost: Each replacement rescans and rebuilds the string, which can already be up to 10^5 long: roughly O(depth · output) or worse.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.