Decode String

Decode text such as 3[a2[c]] into accaccacc.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Decode String: Each [ saves its outer string and repeat count so ] can restore exactly one nesting level.

Input and goalDecode text such as `3[a2[c]]` into `accaccacc`.

Initialize decoder stateBefore scanning 3[a2[c]], stack=[], current="", and repeat=0.

emptytop saved context

input3[a2[c]]layoutouter to innercurrent""repeat0actioninitialize

Recognize it

Use a context stack when repeat counts and bracketed substrings can nest, so finishing an inner region must resume text and count saved before its opening bracket.

Keep true

Before each character, current is the decoded text for the active nesting level, repeat is the number parsed immediately before its next [, and every stack entry preserves one suspended outer (text, count) pair.

Reuse it

When nested work temporarily replaces an outer accumulator, push exactly the outer state needed to resume it; this transfers to expression evaluation, nested tags, and recursive-descent simulation.

Pattern: Stack for nested state.

Simple idea: At [, save the text and repeat count built so far. Start a new inner string. At ], finish the inner string and attach it to the saved outer string.

def decode_string(text: str) -> str:
   stack: list[tuple[str, int]] = []
   current = ""
   repeat = 0

   for char in text:
      if char.isdigit():
         repeat = repeat * 10 + int(char)
      elif char == "[":
         stack.append((current, repeat))
         current, repeat = "", 0
      elif char == "]":
         previous, count = stack.pop()
         current = previous + current * count
      else:
         current += char
   return current

Cost: $O(n+m)$ time and $O(n+m)$ space, where $m$ is the output length.