Decode String
Problem
A string is encoded with the rule k[text], meaning text repeated k times, and these patterns can be nested. Expand the encoding and return the plain string. Digits only ever appear as repeat counts.
Examples
Constraints
- • 1 <= s.length <= 30
- • Repeat counts are in [1, 300]
- • The input is always well-formed
Hints & approach
Hint 1
Nesting means you need to pause an outer string while you build the inner one.
Hint 2
On "[", save the text so far and the pending count.
Hint 3
On "]", repeat the inner text and append it to the saved outer text.
Approachtry the hints first
Scan once, maintaining the current string and a number being parsed. Digits extend the number (counts can have several digits). On "[", push (currentString, count) onto a stack and reset both. On "]", pop (prev, k) and set current = prev + current repeated k times. Letters simply append to current. The final current string is the answer; the stack depth equals the nesting depth.
Time O(output length) · Space O(output length)