AlgoViz
HomeStack

Decode String

Medium

Stack the count and the prefix at each bracket

Problem

Decode a string like 3[a2[c]] where a number k before brackets repeats the bracket content k times.

In simple words

Push counts and partial strings on a stack; a ']' pops and repeats the segment, handling nesting.

The idea

On '[' push the repeat count and the string built so far, then start fresh. On ']' pop them, repeat the current string that many times and append it to the popped prefix. The stack handles arbitrary nesting without recursion.

The trick

  • Two stacks, or one stack of pairs — counts and partial strings.
  • Multi-digit counts must be accumulated before the bracket.
  • Recursion is the same algorithm using the call stack.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

3
2
0
1

Step 1 of 2. Here's the example — 3[a2[c]] Values: 3, 2.

1/2
Optimal
timeO(n)spaceO(n)
1stack2for c: if digit build number; if '[' push (num,current); if ']' pop and repeat; else append

Input

array
[3, 2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "3[a]2[bc]"
Output:
"aaabcbc"
Explanation:
3 a's then 2 bc's → aaabcbc.

Example 2

Input:
s = "3[a2[c]]"
Output:
"accaccacc"
Explanation:
Nested: acc repeated 3 times.

Example 3

Input:
s = "2[abc]"
Output:
"abcabc"
Explanation:
abc twice → abcabc.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.