Decode String: Stack-Based String Building

Decode String is LeetCode 394, rated Medium. It asks you to expand a compressed string where numbers indicate how many times to repeat the content inside brackets. The twist is that brackets can be nested, so you need a way to "remember" the outer context while you work on the inner one. A stack handles that perfectly.

The problem

Given an encoded string, return its decoded string. The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. You can assume the input is always valid: no extra white spaces, brackets are well-formed, and k is always a positive integer.

Input:  "3[a2[c]]"
Output: "accaccacc"

Input:  "3[a]2[bc]"
Output: "aaabcbc"

Input:  "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

The first example is the most interesting because it has nested brackets. 2[c] expands to "cc", then a plus "cc" gives "acc", and 3[acc] gives "accaccacc".

Why a stack works here

When you hit an opening bracket [, you need to save your current progress (the accumulated string and the repeat count) so you can start fresh inside the brackets. When you hit a closing bracket ], you need to retrieve that saved progress, repeat the inner string, and combine it with the outer context.

This "save context, work on inner problem, restore context" pattern is exactly what a stack does. Each level of nesting pushes a new entry, and each closing bracket pops it back.

The algorithm walks through the string character by character:

1. Digit: Build up the repeat count k (it can be multi-digit like 12 or 100).
2. Opening bracket [: Push the current (k, current_str) onto the stack. Reset both to start fresh inside the bracket.
3. Letter: Append it to current_str.
4. Closing bracket ]: Pop (prev_k, prev_str) from the stack. Set current_str = prev_str + current_str * prev_k.

When you finish scanning the string, current_str holds the fully decoded result.

Step-by-step walkthrough

Let's trace through "3[a2[c]]" character by character. Watch how the stack grows when we enter brackets and shrinks when we leave them.

A few things to notice:

• Step 5 is the key moment. When we hit the second [, we push the current state (2, "a") onto the stack. This saves the fact that we had accumulated "a" and need to repeat the upcoming inner result 2 times.
• Step 7 resolves the inner bracket. We pop (2, "a") and compute "a" + "c" * 2 = "acc". The inner nesting is fully resolved.
• Step 8 resolves the outer bracket. We pop (3, "") and compute "" + "acc" * 3 = "accaccacc". The stack is empty, and we have our answer.

The code

Here is the Python solution for LeetCode 394, Decode String:

def decode_string(s: str) -> str:
    stack = []
    current_str = ""
    k = 0

    for ch in s:
        if ch.isdigit():
            k = k * 10 + int(ch)
        elif ch == "[":
            stack.append((k, current_str))
            k = 0
            current_str = ""
        elif ch == "]":
            prev_k, prev_str = stack.pop()
            current_str = prev_str + current_str * prev_k
        else:
            current_str += ch

    return current_str

Let's break down each branch:

• Digit: k = k * 10 + int(ch) handles multi-digit numbers. If the input has 12[a], reading 1 sets k = 1, then reading 2 updates it to k = 1 * 10 + 2 = 12.
• Opening bracket: Push the current (k, current_str) pair, then reset both. Everything inside this bracket starts with a clean slate.
• Closing bracket: Pop the saved pair. The formula prev_str + current_str * prev_k concatenates the string from before the bracket with the repeated inner string.
• Letter: Just append to the working string.

Complexity analysis

Time: O(n * m) where n is the length of the input string and m is the maximum length of the decoded output. Each character is read once in O(n), but string concatenation during the ] step can produce strings proportional to the output size. In the worst case (deeply nested with large multipliers), the output can be much longer than the input.

Space: O(n + m). The stack depth is bounded by the nesting depth, which is at most O(n). The intermediate strings stored on the stack and the final result take space proportional to the output size.

There is no way to avoid O(m) in the output since you have to build the decoded string. The stack approach is optimal for this problem.

The building blocks

This problem is built on one core building block:

Stack-based context save and restore

The pattern of pushing the current state onto a stack when you enter a new scope, working within that scope, and then popping and combining when you leave. In Decode String, the "scope" is defined by brackets, the "state" is the multiplier and accumulated string, and "combining" means repeating and concatenating.

This same save-and-restore pattern drives:

• Valid Parentheses: push openers, pop and validate on closers (simpler version, no state to save beyond the bracket type)
• Basic Calculator: push the current result and sign when you see (, pop and combine when you see )
• Evaluate Reverse Polish Notation: push numbers, pop operands when you see an operator
• Mini Parser / Nested List Weight Sum: push context when entering a nested list, pop when leaving

Every time you see a problem with nested scopes that need to be resolved inside-out, think stack. Decode String is one of the cleanest examples of this pattern because the four character types (digit, [, letter, ]) map directly to the four stack operations (accumulate, push, append, pop-and-combine).

Edge cases

Before submitting, verify your solution handles:

• No nesting: "3[a]2[bc]" should give "aaabcbc". Each bracket pair is independent, no nesting at all.
• Multi-digit multipliers: "10[a]" should give "aaaaaaaaaa". The k = k * 10 + int(ch) formula handles this.
• Bare letters outside brackets: "2[a]bc" should give "aabc". Letters outside any brackets just get appended to the result directly.
• Deeply nested: "2[a2[b2[c]]]" should expand from the inside out. 2[c] becomes "cc", then 2[bcc] becomes "bccbcc", then 2[abccbcc] becomes "abccbccabccbcc".
• Single character, no brackets: "abc" should return "abc". The stack never gets used.

The stack solution handles all of these without special cases. The four-way branch on character type covers every scenario.

From understanding to recall

You have traced through the stack-based approach. You see how each [ pushes state and each ] pops and combines. But can you write the four-way branch and the pop formula from scratch in an interview three weeks from now?

The details that trip people up under pressure are small but critical. Do you push (k, current_str) or (current_str, k)? Do you reset k and current_str after pushing or before? Is the pop formula prev_str + current_str * prev_k or current_str * prev_k + prev_str? And the multi-digit accumulation k = k * 10 + int(ch) is easy to forget if you have only seen single-digit examples.

These are not conceptual gaps. They are recall gaps. Spaced repetition fixes them. You type the decode string solution from scratch at increasing intervals. Each repetition reinforces the push/pop order, the reset logic, and the multi-digit accumulation. After a few cycles, the whole thing is automatic.

Related posts

• Valid Parentheses - The classic stack-based bracket matching problem, using the same push/pop pattern in a simpler context
• Evaluate Reverse Polish Notation - Another stack-based parsing problem where you push values and pop when you encounter operators
• Basic Calculator - Uses the same "save context on open paren, restore on close paren" pattern with arithmetic expressions

CodeBricks breaks the Decode String stack pattern into its reusable building blocks and drills them with spaced repetition. You type the solution from scratch each time, so when LeetCode 394 or any nested expression problem shows up in an interview, the code flows without hesitation.