DSA Tracker

Visualize

Decode String

A stack per '[' remembers where to resume

time O(output length)space O(nesting depth)

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.

Details

Animated on: s = "3[a]2[bc]" — decode a run-length encoded string where k[substring] means substring repeated k times.

Problem:Decode StringMedium

A stack per '[' remembers where to resume

step 1 / 9

3
[0]
[
[1]
a
[2]
]
[3]
2
[4]
[
[5]
b
[6]
c
[7]
]
[8]

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

Every step in words

Show all 9 steps
  1. 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.
  2. '[' at count=3: push (count=3, string="") onto the stack, reset current string.
  3. Letter 'a': append to current string -> "a".
  4. ']': repeat "a" x3 and prepend the saved outer string "" -> "aaa".
  5. '[' at count=2: push (count=2, string="aaa") onto the stack, reset current string.
  6. Letter 'b': append to current string -> "b".
  7. Letter 'c': append to current string -> "bc".
  8. ']': repeat "bc" x2 and prepend the saved outer string "aaa" -> "aaabcbc".
  9. Input fully consumed. Decoded string: "aaabcbc".

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Decode String in the editorAll Stack problemsBack to roadmap