Decode String
Decode String: expand an encoded string of the form k[encoded_string], where the bracketed section repeats exactly k times. Brackets may nest.
- 1 <= s.length <= 30
- s consists of lowercase English letters, digits, and square brackets.
- The input is always valid; 1 <= k <= 300.
Intuition
Nesting means the inner content must finish before the outer repeat can apply, and 'innermost first' is exactly what a stack gives you. Build the current string as you read; on [ push what you had and the repeat count, then start fresh; on ] multiply the piece you just built and glue it back onto the parent.
Nested, balanced delimiters where the inner scope must complete before the outer one is a stack problem — the same shape as expression evaluation, Basic Calculator, and Valid Parentheses. The recognisable move is pushing the context at the opener and restoring it at the closer, so each level is rebuilt from the inside out.
Approach
Before reading on: in "3[a2[c]]", which segment must be resolved first, and what two facts about the outer level do you need to remember while working on the inner one? Aim for one pass.
What has to be remembered at an opening bracket
When you meet [, you are about to start a new inner segment, but two things about the outer context must survive: the text built so far, and how many times this new segment will repeat. Both go on stacks. The current string then resets to empty so the inner segment builds cleanly. Nothing else about the outer level matters, which is why two stacks are enough no matter how deep the nesting goes.
What happens at a closing bracket
A ] means the innermost segment is complete. Pop the repeat count and multiply the segment by it, then pop the saved outer text and append the repeated block to it. That combined value becomes the new current string. Because the pops mirror the pushes exactly, each ] reunites a segment with its own parent — the structure of the brackets is enforced automatically by the stack discipline.
Digits and letters between the brackets
Digits must be accumulated rather than read one at a time: 12[a] means twelve, so build the number with num = num * 10 + int(ch) and only use it when the [ arrives. Plain letters simply append to the current string. After the final character, the current string holds the fully decoded result — no extra pass is needed. Time and space are O(n) in the length of the decoded output, which is what dominates when repeat counts are large.
Solution & live demo
Common pitfalls
Reading digits one character at a time
num = int(ch)
num = num * 10 + int(ch)
Overwriting instead of accumulating breaks any count of two or more digits: 12[a] keeps only the 2 and produces two copies instead of twelve.
Concatenating in the wrong order on close
current = current * count_stack.pop() + string_stack.pop()
current = string_stack.pop() + current * count_stack.pop()
The saved outer text came before the bracket, so it must be the prefix. Reversing the order turns "a2[b]" into "bba" instead of "abb".
Forgetting to reset num after pushing
count_stack.append(num) string_stack.append(current) current = ""
count_stack.append(num) string_stack.append(current) current, num = "", 0
A stale num leaks into the next bracket group, so 2[a]3[b] may apply the wrong multiplier — the count must be consumed and cleared at the same moment it is pushed.
Edge cases
Letters append directly and the stacks stay empty; the input is returned unchanged.
Digits accumulate into 12 before the bracket, producing twelve copies rather than one then two.
The inner 2[c] resolves to 'cc' first, then the outer repeat applies to 'acc'.
The trailing letters append to the already-decoded string, giving 'ababcd'.
Multiplying by zero yields an empty block, which appends harmlessly.