hardStack / QueuePure DSA~30 min
Expand a Run-Length Encoded String With Nesting
A compact template uses the form k[token] to mean 'repeat token k times', and templates may nest. Expand the template into its full string.
Problem
Given an encoded string s following the rule k[encoded_string] meaning the bracketed content repeats k times (with arbitrary nesting), return the decoded string. The input is always valid; k is a positive integer; original content has no digits.
Input
An encoded string s.
Output
The fully expanded string.
Constraints
- 1 <= s.length <= 30
- Brackets are balanced and the encoding is well-formed.
- 1 <= k <= 300; expanded length stays manageable.
Examples
Example 1
Input
s = "3[a]2[bc]"
Output
"aaabcbc"
a repeats 3 times, bc repeats twice.
Example 2
Input
s = "3[a2[c]]"
Output
"accaccacc"
Inner 2[c] -> cc, then 3[acc].