Decode String — LC 394 Stack-Based Expansion

Problem Statement#

Given an encoded string of the form k[encoded_string], return its expansion. Brackets can nest. k is always a positive integer.

Constraints:

• 1 <= s.length <= 30
• s contains lowercase letters, digits, [, ]
• Test cases avoid output longer than 10^5

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

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

Why This Problem Matters#

LC 394 is a heavily rotated string FAANG problem at Google, Amazon, and ByteDance. It tests your ability to track nested state — a skill that transfers directly to expression parsing, JSON tokenizers, and template engines.

The naive approach of recursive replace blows up on nested groups like 2[3[a]2[b]]. Recruiters use this question to filter candidates who can spot the LIFO structure of brackets and reach for a stack without prompting. If you have ever debugged a parser, the pattern is instantly familiar.

The Core Insight#

Nested brackets are the textbook use case for a stack. We push state onto the stack every time we see [, build the inner string, then pop and combine when we see ].

Two stacks make the bookkeeping clean: one for the multiplier k, one for the partial string built so far. When [ arrives, we save current state and reset. When ] arrives, we pop the count and the saved prefix, then concatenate prefix + current * k.

Visual Dry Run#

For s = "3[a2[c]]":

Solution (Optimal)#

class Solution:
    def decodeString(self, s: str) -> str:
        count_stack = []
        str_stack = []
        cur_str = ""
        cur_count = 0
        for ch in s:
            if ch.isdigit():
                cur_count = cur_count * 10 + int(ch)
            elif ch == "[":
                count_stack.append(cur_count)
                str_stack.append(cur_str)
                cur_count = 0
                cur_str = ""
            elif ch == "]":
                k = count_stack.pop()
                prev = str_stack.pop()
                cur_str = prev + cur_str * k
            else:
                cur_str += ch
        return cur_str

var decodeString = function(s) {
    const countStack = [];
    const strStack = [];
    let curStr = "";
    let curCount = 0;
    for (const ch of s) {
        if (ch >= '0' && ch <= '9') {
            curCount = curCount * 10 + (ch.charCodeAt(0) - 48);
        } else if (ch === '[') {
            countStack.push(curCount);
            strStack.push(curStr);
            curCount = 0;
            curStr = "";
        } else if (ch === ']') {
            const k = countStack.pop();
            const prev = strStack.pop();
            curStr = prev + curStr.repeat(k);
        } else {
            curStr += ch;
        }
    }
    return curStr;
};

Time: O(n * maxK) — each char of the output is produced once. Space: O(n) — for both stacks at maximum nesting depth.

Common Mistakes#

• Treating each digit independently — forgetting k can be multi-digit like 100[a].
• Resetting curStr before pushing — push first, then reset.
• Using a single stack of mixed types and getting type errors at pop time.
• Recursive replace calls that re-process already-expanded substrings.
• Forgetting that letters appearing before [ belong to the outer scope.

Interview Tips#

• Mention both stack and recursion approaches; the stack scales better.
• Walk through 3[a2[c]] on the whiteboard before coding.
• Call out the multi-digit number gotcha early.
• If asked, write a recursive variant that returns decoded plus index for completeness.

Follow-up Questions#

• What if the input can be malformed? Add bracket-balance validation.
• Encode the inverse: shortest encoding of a repeated pattern (LC 471).
• Streaming input — process char-by-char without buffering the whole string.
• Negative or zero multiplier behavior — clarify before coding.
• Output length cap of 10^5 — when to bail with overflow detection.

Key Takeaways#

• Nested brackets always suggest a stack-based parse.
• Use one stack for counts and one for prefix strings to keep state clean.
• Build numbers digit-by-digit so 100[a] works.
• Reset curCount and curStr after pushing them at [.
• Pop and concatenate prev + curStr * k at ].
• Time is O(output length); space is O(nesting depth).
• The stack pattern generalizes to expression parsers and template engines.