Algorithm

Decode String

Stacks & Queues Pattern

Decode String

Given an encoded string, return its decoded string (e.g., 3[a]2[bc] -> aaabcbc).

CONSTRAINTS
  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets
  • s is guaranteed to be a valid input
EXAMPLE 1
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
EXAMPLE 2
Input: s = "3[a2[c]]"
Output: "accaccacc"
Could the repeat count 'k' be zero or very large?
Yes, we must parse 'k' iteratively to handle multi-digit numbers. If k=0, the bracket content should be skipped (yields an empty string).
What if the input contains nested brackets like '2[a3[b]]'?
Nested brackets represent sub-problems that must be fully expanded before the outer string can be completed. We treat each '[' as a signal to save our current progress (the string built so far and its multiplier) and start a fresh decoding for the inner content. Once the inner bracket ']' closes, we merge its result back into the saved state and resume.

When you see a pattern like 3[a2[c]], you are looking at a Dependency Chain. You want to repeat something 3 times, but that something is not fully known yet—it is a plus whatever 2[c] turns into. You are stuck in a waiting game: you cannot finish the outer 3 expansion until you have completely finished the inner 2 expansion first.

This Last-In, First-Resolved priority is why a Stack is needed. It allows us to put our current task on a shelf and focus entirely on the newest sub-task that just appeared. Once the sub-task is done, we grab the old task back off the shelf and merge the result.

Pause and Resume

We move through the string one character at a time, keeping a Current Workspace (the string we are building) and a Current Multiplier (the number we just read).
- The '[' (Enter New Sub-Task): We have hit a nested pattern! We cannot finish our current work yet. We Push our Current Workspace and Current Multiplier onto the Stack for safekeeping. Then, we clear our workspace to start fresh on the inner pattern.
- Alphabet Letters: Just keep building the string in your Current Workspace.
- The ']' (Finish Sub-Task): We have finished an inner pattern! Now we must merge it back.
- Pop the saved multiplier and the saved Previous Workspace from the Stack.
- Multiply our finished inner string by the multiplier.
- Glue it onto the end of the Previous Workspace.
- Our Current Workspace is now this merged result.

Code Blueprint
text
stack = []
current_string = ""
current_multiplier = 0

FOR each character in string:
    IF character is a Digit:
        current_multiplier = (current_multiplier * 10) + digit
    ELSE IF character is '[':
        // PAUSE: Save context
        stack.PUSH([current_string, current_multiplier])
        current_string = ""
        current_multiplier = 0
    ELSE IF character is ']':
        // RESUME: Pop and expand
        [prev_string, num] = stack.POP()
        current_string = prev_string + (current_string * num)
    ELSE:
        current_string += character

RETURN current_string
Worked Example:3[a2[c]]
0
('', 3)
Top
Scan '3[': We pause decoding. Push multiplier 3 and parent string '' onto the stack as ('', 3). Reset currentString = ''.
0
('', 3)
Scan 'a': Character. Append to currentString. Stack remains [('', 3)]. currentString = 'a'.
0
('', 3)
1
('a', 2)
Top
Scan '2[': We pause decoding. Push multiplier 2 and parent string 'a' onto the stack as ('a', 2). Reset currentString = ''.
0
('', 3)
1
('a', 2)
Scan 'c': Character. Append to currentString. Stack remains [('', 3), ('a', 2)]. currentString = 'c'.
0
('', 3)
Top
Scan ']': Closing bracket. Pop top state ('a', 2). Multiply currentString 'c' by 2 and prepend parent 'a' -> 'a' + ('c' * 2) = 'acc'. currentString becomes 'acc'.
Scan ']': Closing bracket. Pop top state ('', 3). Multiply currentString 'acc' by 3 and prepend parent '' -> '' + ('acc' * 3) = 'accaccacc'. Done!
Interactive Strategy Visualization
RECURSIVE DECODING INSIGHT

Dual-Stack Checkpointing for Nested Structures

Input expression tape
3
[
a
]
2
[
b
c
]
Count Stack
Result Stack
Current Building Segment
""
Strategy Execution

Decoding '3[a]2[bc]'. Prepare stacks for nested expansion.

Checkpoint & Restore

Use stacks to "checkpoint" the current state (string and multiplier) before diving into a nested bracket.

O(N × maxK) Output-Sized · Stack Holds Paused Jobs