Decode String

Problem in simple words

Given an encoded string like "3[a]2[bc]", decode it by expanding each bracketed segment its given number of times.

Core idea

Nested encoded strings need a stack because the innermost segment finishes first.

How the algorithm thinks

1. 1

   Build up the current segment and repeat count

   VISIT

   Characters and digits accumulate into the current segment and count until a bracket changes context.

   Watch: The current segment text and accumulated count.

2. 2

   Save context when a new segment opens

   PUSH

   Entering a new bracket means the enclosing prefix and count need to be remembered for later.

   Watch: What's pushed onto the prefix and count stacks.

3. 3

   Expand and restore context when a segment closes

   POP

   Closing a bracket means the just-finished segment can now be repeated and combined with its saved outer prefix.

   Watch: The expanded segment and the restored outer prefix.

4. 4

   Return the fully decoded string

   RETURN

   Once every bracket has been matched and expanded, the current segment holds the complete decoded string.

   Watch: The final decoded string.

Step-by-step logic

• -Scan the encoded string one character at a time, tracking a current decoded segment and an accumulating repeat count.
• -On a digit, add it to the current repeat count (to handle multi-digit numbers).
• -On '[', push the current count and prefix onto separate stacks, then reset the current segment and count.
• -On ']', pop the saved count and prefix, and set the current segment to the saved prefix plus the current segment repeated that many times; on any other character, just append it to the current segment.

Complexity

Time O(n + output)·Space O(n + output)

the parser scans each token and materializes the decoded output.

Implementation

This is the JavaScript implementation that generates the simulator timeline.

function decodeString(input) {
  push count and prefix at '[';
  pop and repeat segment at ']';
}

Common mistakes