Decode String — Two-Stack for Nested Encodings

Problem Statement#

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 may assume the input is always valid and there are no extra white spaces.

Constraints:

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[]'.
• s is guaranteed to be a valid input.
• All integers in s are in the range [1, 300].

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

Input:  s = "3[a2[c]]"
Output: "accaccacc"
Explanation: Inner 2[c] = "cc"; outer 3[a+cc] = 3[acc] = "accaccacc"

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

Why This Problem Matters#

LC 394 is a medium-difficulty problem asked at Google, Amazon, and Facebook that teaches nested structure parsing with a stack. The same technique powers:

• JSON parsers: nested objects and arrays.
• Compilers: parsing nested expressions and function calls.
• Valid Parentheses (LC 20): bracket matching.
• Basic Calculator (LC 224, 227): nested arithmetic expression evaluation.
• Flatten Nested List Iterator (LC 341): same stack-based nesting traversal.

The core skill tested: maintaining multiple pieces of state across nesting levels. When you open a bracket ([), you save the current state (the partial string and the count). When you close a bracket (]), you restore the saved state and apply the repetition.

The Core Insight#

The encoding is recursive: k[encoded_string] where encoded_string can itself contain more k[encoded_string] patterns. A stack is the perfect structure for recursive nesting.

State at each nesting level:

• cur_str: the string being built at this level.
• cur_num: the current repetition count for the next [...] block.

At [: Save (cur_str, cur_num) to the stack; reset both for the new inner level. At ]: Pop (prev_str, num) from stack; cur_str = prev_str + num * cur_str. Digit: Accumulate multi-digit numbers: cur_num = cur_num * 10 + int(c). Letter: Append to cur_str.

Visual Dry Run#

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

Result: "accaccacc" ✓

Solution (Optimal)#

# Python — two-stack approach (count stack + string stack), O(output) time
def decodeString(s: str) -> str:
    stack = []    # stores (partial_string, repeat_count) pairs
    cur_str = ''  # string being built at the current nesting level
    cur_num = 0   # current number being accumulated
 
    for c in s:
        if c.isdigit():
            # Accumulate multi-digit numbers (e.g., 12 = 1*10 + 2)
            cur_num = cur_num * 10 + int(c)
        elif c == '[':
            # Opening bracket: save current state, start fresh for inner level
            stack.append((cur_str, cur_num))
            cur_str = ''
            cur_num = 0
        elif c == ']':
            # Closing bracket: restore outer state and apply repetition
            prev_str, num = stack.pop()
            cur_str = prev_str + num * cur_str
        else:
            # Regular letter: append to current string
            cur_str += c
 
    return cur_str

// JavaScript — two-stack approach, O(output) time
function decodeString(s) {
    const stack = [];   // stores [partial_string, repeat_count] pairs
    let curStr = '';
    let curNum = 0;
 
    for (const c of s) {
        if (c >= '0' && c <= '9') {
            curNum = curNum * 10 + parseInt(c, 10);
        } else if (c === '[') {
            stack.push([curStr, curNum]);
            curStr = '';
            curNum = 0;
        } else if (c === ']') {
            const [prevStr, num] = stack.pop();
            curStr = prevStr + curStr.repeat(num);
        } else {
            curStr += c;
        }
    }
 
    return curStr;
}

Complexity:

Note: the output can be much larger than the input (e.g., 100[100[100[a]]] produces 10^6 characters). The time complexity is proportional to the output size.

Common Mistakes#

1. Accumulating multi-digit numbers incorrectly. "12[a]" has repetition count 12, not 1 then 2. Use cur_num = cur_num * 10 + int(c) to accumulate digits properly.

2. Pushing only the string or only the count to the stack. You need both (partial_string, repeat_count) to correctly restore state at ]. Losing either piece breaks the reconstruction.

3. Applying num * cur_str before prepending prev_str. The restored string is prev_str + num * cur_str, not num * cur_str + prev_str. Order matters for non-symmetric strings.

4. Not resetting cur_num to 0 after [. If you open two nested brackets in sequence without resetting, the inner count bleeds into the outer level.

5. Using recursion and hitting Python's stack limit. For deeply nested strings, Python's default recursion limit (1000) may be exceeded. The iterative approach avoids this issue entirely.

Interview Tips#

• Connect to Valid Parentheses: "This is the generalized form of bracket matching — instead of just matching, we need to restore and apply a repetition count at each level."
• Explain the save-and-restore pattern: "At [, I save my current state (partial string and count) and reset for the inner block. At ], I restore the outer state and expand the inner block."
• Mention multi-digit numbers: "The digit accumulation cur_num = cur_num * 10 + int(c) handles counts like 12 or 300 correctly."

Follow-up Questions#

1. Encode a string using the k[s] format. This is the reverse — find repeated substrings and compress them.
2. What if the encoding can have letters before the first bracket? The current solution handles this: letters before any [ go directly into cur_str.
3. What if counts can be zero? 0[abc] should produce an empty string. num * cur_str handles this: 0 * "abc" = "".
4. Flatten Nested List Iterator (LC 341) — similar stack-based approach for nested structure traversal.
5. Count distinct substrings of the decoded string. Decode first (potentially huge output), then use suffix arrays or hashing to count distinct substrings.

Key Takeaways#

• Use a stack of (partial_string, repeat_count) pairs to handle nesting: save state on [, restore and expand on ].
• Multi-digit number accumulation: cur_num = cur_num * 10 + int(c) — process all digit characters before [.
• Reconstructed string order: prev_str + num * cur_str — prepend the outer string, not append.
• Always reset both cur_str and cur_num to their defaults when pushing to the stack at [.
• This is the iterative alternative to recursion — avoids Python's call stack limit and is O(depth) space instead of O(output) space.
• The same save-and-restore pattern applies to JSON parsing, compiler expression evaluation, and any nested structure traversal.