Visualize

Pattern visualizer

Decode String

The tricky part is NESTED brackets — 3[a2[c]] needs the inner expansion done first. A stack solves this the same way it solves any nested-structure problem: every '[' saves the current progress (the count and the string built so far) and starts a fresh scope; every ']' pops that saved state, repeats what was just built, and glues it onto what came before — naturally unwinding the nesting from the inside out. Animated on: s = "3[a]2[bc]" — decode a run-length encoded string where k[substring] means substring repeated k times..

A stack per '[' remembers where to resume

time O(output length)space O(nesting depth)step 1 / 9
3
[0]
[
[1]
a
[2]
]
[3]
2
[4]
[
[5]
b
[6]
c
[7]
]
[8]
line 2

s="3[a]2[bc]". A stack handles the nesting: when we hit '[', push the current count + string-so-far and start fresh; when we hit ']', pop and repeat.

Pseudocode
1FUNCTION decodeString(s):
2  countStack, stringStack are empty stacks; current = '', num = 0
3  FOR each character ch in s:
4    IF ch is a digit: num = num*10 + ch
5    ELSE IF ch is '[': push num and current onto the stacks; reset current to '' and num to 0
6    ELSE IF ch is ']': pop the saved count and string; current = savedString + current repeated count times
7    ELSE: append ch to current
8  RETURN current

← / → step · space play · Home restart

Where to practice Stack

Practice Stack problemsAll Stack problemsBack to roadmap