Decode String LeetCode 394 Deep Dive

LeetCode 394 — Decode String — presents an encoding scheme where a number immediately before a pair of brackets means the enclosed substring should be repeated that many times. For example, "3[a2[c]]" decodes to "accaccacc": the inner "2[c]" decodes to "cc", so the bracket contents become "acc", and "3[acc]" becomes "accaccacc". The encoding is well-formed — brackets are always matched and numbers are always positive integers.

The key challenge is nesting. Brackets can appear inside other brackets to arbitrary depth, and the outer repeat count applies to the fully decoded inner string, not the raw encoded form. This makes a purely iterative character-by-character approach with no auxiliary state insufficient — you need a way to save and restore context as you enter and exit each bracket level.

This problem is a canonical example of the stack-as-context-save pattern used across many bracket-parsing problems. Understanding it deeply equips you to handle basic calculator, evaluate reverse polish notation, and any grammar with nested recursive structure.

The stack-based solution tracks two running variables: currentString (the string being built for the current bracket level) and currentNum (the number accumulated from consecutive digit characters). As you scan each character, you update these variables or interact with the stack depending on what you see.

When you encounter an opening bracket "[", you push the pair (currentString, currentNum) onto the stack and reset both variables to empty string and zero. This saves your context before descending into the nested level. When you encounter a closing bracket "]", you pop (prevString, count) from the stack and set currentString = prevString + currentString * count. This restores the outer context and appends the fully decoded inner result repeated the correct number of times.

Digits accumulate into currentNum using num = num*10 + int(ch) to handle multi-digit repeat counts. Letters append directly to currentString. The stack depth equals the nesting depth of the input; at the end, currentString holds the final decoded result.

The algorithm processes the input string left to right one character at a time. There are exactly four cases: the character is a digit, a lowercase letter, an opening bracket, or a closing bracket. Each case has a simple, focused action — there is no look-ahead needed.

Digit handling is the subtlest case. Because repeat counts can be multi-digit (e.g., "12[a]" means twelve repetitions), you cannot treat each digit character as a standalone number. Instead, you accumulate with num = num * 10 + int(ch), building the full integer before you see the "[". A fresh scan of consecutive digit characters before each bracket produces the correct multi-digit count.

Letter handling is the simplest: append the character to currentString. This covers all non-digit, non-bracket characters in a valid input. The four cases are exhaustive for valid input, so a simple if/elif/else chain or switch handles all logic without edge case branching beyond these four.

The recursive approach treats the encoded string as a context-free grammar and decodes it by consuming characters through a global index. A function decode() reads characters starting at the current index. When it encounters digits, it reads the full number. When it encounters "[", it recursively calls decode() to decode the inner string, then repeats it. When it encounters a letter, it appends to the current result. When it encounters "]" or reaches the end of input, it returns the current result and the current index.

The recursion depth equals the nesting depth of the input. Each recursive call handles exactly one bracket level, returning both the decoded string for that level and the position in the input where that level ended. The caller uses the returned index to continue scanning after the closing bracket.

The iterative stack solution and the recursive solution are functionally identical — the call stack in the recursive version plays the same role as the explicit stack in the iterative version. The iterative approach is preferred in production code to avoid stack overflow on deeply nested inputs, but the recursive version is often cleaner to reason about during interviews.

Trace through "3[a2[c]]" step by step. Characters: "3", "[", "a", "2", "[", "c", "]", "]". Start: currentString="", currentNum=0, stack=[].

"3": digit → currentNum=3. "[": push ("", 3); reset currentString="", currentNum=0. "a": letter → currentString="a". "2": digit → currentNum=2. "[": push ("a", 2); reset currentString="", currentNum=0. "c": letter → currentString="c". "]": pop ("a", 2); currentString = "a" + "c"*2 = "a"+"cc" = "acc". "]": pop ("", 3); currentString = "" + "acc"*3 = "accaccacc".

Final currentString = "accaccacc" — the correct decoded output. Note how the inner "]" resolved the "2[c]" subproblem first (producing "cc"), then the outer "]" resolved "3[a...]" using the already-decoded inner result. The stack ensures inner brackets are always resolved before outer ones.

Python implementation: stack = []; currentString = ""; currentNum = 0; then iterate each ch in s. If ch.isdigit(): currentNum = currentNum*10 + int(ch). Elif ch.isalpha(): currentString += ch. Elif ch == "[": stack.append((currentString, currentNum)); currentString = ""; currentNum = 0. Else (ch == "]"): prevString, count = stack.pop(); currentString = prevString + currentString * count. Return currentString. Time complexity: O(n * maxRepeat) where n is output length; space: O(n) for the stack and strings.

Java implementation: Deque<Object[]> stack = new ArrayDeque<>(); StringBuilder currentString = new StringBuilder(); int currentNum = 0; then iterate each char ch. If Character.isDigit(ch): currentNum = currentNum*10 + (ch-'0'). Else if Character.isLetter(ch): currentString.append(ch). Else if ch == '[': stack.push(new Object[]{currentString.toString(), currentNum}); currentString = new StringBuilder(); currentNum = 0. Else (ch == ']'): Object[] top = stack.pop(); String prev = (String)top[0]; int count = (int)top[1]; String inner = currentString.toString(); currentString = new StringBuilder(prev); for(int i=0;i<count;i++) currentString.append(inner). Return currentString.toString().

Both implementations store (String, int) pairs on the stack. The critical Java note is to use StringBuilder for efficiency — naive String concatenation inside a loop is O(n^2) for string building. Python string multiplication (s * k) creates a new string in O(k * len(s)) time which is unavoidable but optimal for this problem structure.

Basic Calculator — LeetCode 224 — applies the same stack-as-context pattern to arithmetic expressions with parentheses. Instead of (string, count) pairs on the stack, you push (result, sign) pairs when entering a parenthesized subexpression and restore them on the closing parenthesis. The structural similarity is exact: brackets delimit subproblems, the stack saves context, and closing brackets trigger a pop-and-merge.

Evaluate Reverse Polish Notation — LeetCode 150 — uses a stack in the opposite direction: operands are pushed and operators pop two operands, compute, and push the result. There are no nested brackets, but the stack still manages the pending computation context. Valid Parentheses — LeetCode 20 — is the simplest bracket problem, using a stack only to track unmatched opening brackets without computing any result.

Together, Decode String, Basic Calculator, and Evaluate RPN form the bracket-parsing family. Decode String teaches push-on-open / pop-on-close with string context. Basic Calculator adds arithmetic operators to the context. Evaluate RPN removes brackets entirely and uses postfix notation. Mastering all three gives you a complete toolkit for expression and grammar parsing problems in interviews.