mediumStack / QueuePure DSA~25 min
Expand A Nested Repeat-Encoded String
A compact config format encodes repetition as k[segment], where segment is repeated k times and may itself contain nested encodings. Decode it to the fully expanded string.
Problem
Given an encoded string s using the rule k[encoded_substring], return its decoded form. k is a positive integer; brackets are always well-formed and may nest. The input contains only digits, letters, and brackets.
Input
An encoded string s.
Output
The decoded string.
Constraints
- 1 ≤ |s| ≤ 30
- 1 ≤ k ≤ 300
- Letters are lowercase English; brackets are balanced.
- The decoded output fits comfortably in memory.
Examples
Example 1
Input
s="3[a]2[bc]"
Output
aaabcbc
'a' three times then 'bc' twice.
Example 2
Input
s="3[a2[c]]"
Output
accaccacc
Inner 2[c] expands to 'cc', so 'acc' repeated three times.