String Building / Simulation

Before we start

You have used stacks to track matching brackets. This chapter shows a second stack superpower: saving state when entering a nested context and restoring it when leaving. This is how recursion works — and a stack lets you simulate recursion without the function-call overhead. By the end you will be able to:

• Decode nested repetition strings like "3[a2[bc]]" in O(n) time.
• Explain exactly what the stack stores and why it needs two lanes (string + count).
• Adapt the same skeleton to expression evaluation and text-editor simulation.

Picture this first (no code yet)

The actual problem

Decode String (LC #394):

Given s = "3[a2[bc]]", decode it to produce the repeated string.

"3[a2[bc]]" → "abcbcabcbcabcbc"

Why? 2[bc] → "bcbc". a2[bc] → "abcbc". 3[abcbc] → "abcbcabcbcabcbc".

The brackets can nest arbitrarily deep. That "arbitrarily deep" is the signal that a stack (or recursion) is the right tool.

First, the slow way (so you feel the pain)

You could try to resolve the innermost brackets first by scanning for the deepest [, expanding it, and repeating. For a string like "2[2[2[a]]]" you would need 3 passes — O(n × depth). For depth 100 and n = 10 000, that is 1 million operations that should be 10 000. And the string grows with each pass, making later passes slower. The stack approach does it in one pass.

The turning point

The one idea to remember

Watch it happen, frame by frame

Input: "3[a2[bc]]"

current_str = ""    current_num = 0    stack = []

ch='3': digit → current_num = 3
ch='[': push ("", 3) → stack=[("", 3)]. Reset: current_str="", current_num=0
ch='a': letter → current_str = "a"
ch='2': digit → current_num = 2
ch='[': push ("a", 2) → stack=[("",3),("a",2)]. Reset: current_str="", current_num=0
ch='b': current_str = "b"
ch='c': current_str = "bc"
ch=']': pop ("a", 2). current_str = "a" + "bc" × 2 = "a" + "bcbc" = "abcbc"
ch=']': pop ("", 3). current_str = "" + "abcbc" × 3 = "abcbcabcbcabcbc"

Answer: "abcbcabcbcabcbc"  ✅

Every character is touched exactly once. O(n) time.

The code, line by line

def decodeString(s: str) -> str:
    stack       = []     # each entry: (string_built_before_this_bracket, repeat_count)
    current_str = ""     # string being built at current depth
    current_num = 0      # number being accumulated (may be multi-digit: "12[a]")

    for ch in s:
        if ch.isdigit():
            current_num = current_num * 10 + int(ch)   # handle multi-digit numbers
        elif ch == '[':
            stack.append((current_str, current_num))   # save state
            current_str = ""                           # start fresh inside bracket
            current_num = 0
        elif ch == ']':
            saved_str, repeat = stack.pop()            # restore state
            current_str = saved_str + current_str * repeat
        else:
            current_str += ch                          # regular character

    return current_str

• current_num * 10 + int(ch) — multi-digit support. "12[" processes 1 first (current_num=1), then 2 (current_num = 1×10 + 2 = 12). Essential — don't just do current_num = int(ch).
• stack.append((current_str, current_num)) — saves the outer context before diving into the inner bracket.
• current_str = saved_str + current_str * repeat — "the outer string so far" + "the inner string repeated count times." The order matters: outer comes first.

Variant: Basic Calculator II (LC #227)

Evaluate a string like "3+2*2" or " 3/2 " following standard operator precedence (no parentheses).

def calculate(s: str) -> int:
    stack  = []
    num    = 0
    sign   = '+'     # the pending operator before the current number

    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)

        if (not ch.isdigit() and ch != ' ') or i == len(s) - 1:
            # time to apply the pending sign
            if sign == '+':   stack.append(num)
            elif sign == '-': stack.append(-num)
            elif sign == '*': stack.append(stack.pop() * num)
            elif sign == '/': stack.append(int(stack.pop() / num))  # truncate toward 0
            sign = ch
            num  = 0

    return sum(stack)

The insight: + and - push numbers onto the stack (deferred addition). * and / apply immediately by popping and pushing (they bind tighter). At the end, sum everything on the stack.

Frame-by-frame: "3+2*2"

ch='3': num=3
ch='+': sign was '+' → push 3. stack=[3]. sign='+', num=0
ch='2': num=2
ch='*': sign was '+' → push 2. stack=[3,2]. sign='*', num=0
ch='2': num=2 (last char)
  end:  sign was '*' → stack.pop()=2, push 2*2=4. stack=[3,4]

sum([3,4]) = 7  ✅

Variant: Backspace String Compare / Text Editor Simulation

A stack naturally simulates a text editor with backspace (#):

def processTyped(typed: str) -> str:
    stack = []
    for ch in typed:
        if ch == '#':
            if stack: stack.pop()    # backspace — delete last character
        else:
            stack.append(ch)
    return "".join(stack)

This is O(n) time and O(n) space. Every character is pushed once and popped at most once.

The skeleton for all nested-decode problems

stack = []
current_context = initial_state

for ch in s:
    if ch is "open" signal:
        stack.append(current_context)    # save outer state
        current_context = fresh_state    # start inner context
    elif ch is "close" signal:
        outer = stack.pop()              # restore outer state
        current_context = combine(outer, current_context)
    else:
        update current_context with ch

The specific types of context, fresh_state, and combine depend on the problem. For Decode String: context = (string, count), combine = outer_string + inner_string * count.

Where to spot this pattern

Trigger words:

• "decode" with repeated/nested structure like "3[a2[bc]]"
• "evaluate expression" with parentheses or operator precedence
• "simulate" a process step by step (text editor, robot path)
• "nested" — any nesting signals a stack-based approach

5 disguises:

1. Decode String (LC #394): the canonical example — push/pop (string, count).
2. Basic Calculator (LC #224): parentheses + +/- — stack of running sums per depth level.
3. Basic Calculator II (LC #227): no parentheses, all operators — stack-based precedence handling.
4. Mini Parser (LC #385): parse a nested list — stack of NestedInteger objects.
5. Robot Return to Origin (LC #657): simulate moves, track position. Simple counter — no stack needed. Contrast to know when stack is necessary.

Common traps

stack = [];  cur_str = "";  cur_num = 0

for ch in s:
    if ch.isdigit():
        cur_num = cur_num * 10 + int(ch)     # multi-digit!
    elif ch == '[':
        stack.append((cur_str, cur_num))
        cur_str, cur_num = "", 0
    elif ch == ']':
        saved, repeat = stack.pop()
        cur_str = saved + cur_str * repeat   # outer THEN inner×repeat
    else:
        cur_str += ch

Check yourself

cur="", num=0, stack=[]

'2': num=2
'[': push("",2). cur="", num=0
'a': cur="a"
'b': cur="ab"
'c': cur="abc"
']': pop("",2). cur = "" + "abc"*2 = "abcabc"
'3': num=3
'[': push("abcabc",3). cur="", num=0
'c': cur="c"
'd': cur="cd"
']': pop("abcabc",3). cur = "abcabc" + "cd"*3 = "abcabccdcdcd"
'e': cur="abcabccdcdcde"
'f': cur="abcabccdcdcdef"

Output: "abcabccdcdcdef"  ✅

Practice problems

Next up: Anagram Pattern — why two strings are anagrams, three ways to check it, and how sliding-window anagram detection works in O(n).