Decode String: LeetCode 394 Stack Solution Explained

If Valid Parentheses teaches you that stacks can match brackets, Decode String (#394) teaches you that stacks can save and restore context. This single problem captures the core mechanic behind expression parsers, recursive descent compilers, and every system that processes nested structures.

The decode string leetcode problem asks you to expand an encoded string like "3[a2[c]]" into "accaccacc". Numbers before brackets indicate how many times to repeat the enclosed substring. Brackets can nest arbitrarily deep, which is exactly what makes this problem interesting — and why a stack is the perfect tool.

Once you understand how to push context on "[" and pop-and-build on "]", you will recognize this pattern in dozens of other problems. It is the same mechanic used in Basic Calculator, nested list deserialization, and HTML tag matching.

You are given an encoded string where the pattern k[encoded_string] means the encoded_string inside the brackets is repeated exactly k times. The encoding can be nested, so you might see numbers and brackets inside other brackets.

Consider the input "3[a2[c]]". The inner bracket "2[c]" expands to "cc". That gives you "3[acc]", which expands to "accaccacc". The nesting means you cannot simply scan left to right and expand — you need to handle the innermost brackets first and work outward.

The constraints guarantee that the input is always valid: every "[" has a matching "]", every number is followed by "[", and the encoded string contains only lowercase letters, digits, and brackets. This means you do not need error handling for malformed input.

The key insight is that every "[" starts a new context and every "]" closes the current context and merges it back into the previous one. A stack lets you save the previous context before entering a bracket and restore it when you exit.

You maintain two pieces of state as you scan left to right: the current string being built and the current number being accumulated. When you encounter "[", you push both the current string and the current number onto the stack, then reset both. When you encounter "]", you pop the previous string and the previous count, then set your current string to previous_string + current_string repeated count times.

For letters, you simply append them to the current string. For digits, you accumulate them into the current number (to handle multi-digit numbers like "10" or "123"). This four-way character classification — digit, letter, "[", "]" — is all you need.

The implementation uses two stacks — one for saved counts and one for saved strings — or equivalently a single stack of pairs. You also maintain two variables: currentString (the string being built in the current bracket scope) and currentNum (the number being accumulated from consecutive digits).

Walk through each character in the input. If the character is a digit, update currentNum: currentNum = currentNum * 10 + parseInt(char). This handles multi-digit numbers naturally. If the character is a letter, append it to currentString.

If the character is "[", push currentString and currentNum onto their respective stacks, then reset currentString to empty and currentNum to zero. You are now inside a new bracket scope, building a fresh substring.

If the character is "]", pop the previous count and previous string from the stacks. Set currentString = previousString + currentString.repeat(count). You have just exited a bracket scope and merged its expanded result back into the parent scope.

Let us trace the decode string stack algorithm on the classic example "3[a2[c]]". This visual walkthrough makes the push-and-pop mechanics concrete.

Character "3": it is a digit, so currentNum = 3. Character "[": push ("", 3) onto the stacks. Reset currentString = "", currentNum = 0. We are now inside the first bracket scope. StringStack: [""], CountStack: [3].

Character "a": it is a letter, so currentString = "a". Character "2": it is a digit, so currentNum = 2. Character "[": push ("a", 2) onto the stacks. Reset currentString = "", currentNum = 0. We are now inside the nested second bracket scope. StringStack: ["", "a"], CountStack: [3, 2].

Character "c": currentString = "c". Character "]": pop count = 2 and prevString = "a". Set currentString = "a" + "c".repeat(2) = "a" + "cc" = "acc". StringStack: [""], CountStack: [3]. We exited the inner bracket.

Character "]": pop count = 3 and prevString = "". Set currentString = "" + "acc".repeat(3) = "accaccacc". Both stacks are empty. We exited the outer bracket. The final result is "accaccacc".

The simplest edge case is no nesting at all: "3[a]" expands to "aaa". Your code handles this naturally — one push on "[", one pop on "]", done. No special logic needed.

Adjacent brackets like "2[a]3[b]" produce "aabb" followed by "bbb", giving "aabbb". After the first "]" closes and merges, currentString is "aa". The "3" starts accumulating a new number, and the second "[" pushes "aa" onto the stack. When the second "]" pops, you get "aa" + "b".repeat(3) = "aabbb".

Deeply nested brackets like "2[a2[b2[c]]]" work correctly because each "[" pushes context and each "]" pops it. The innermost "2[c]" expands to "cc", then "2[bcc]" expands to "bccbcc", then "2[abccbcc]" expands to "abccbccabccbcc". The stack handles arbitrary depth.

Decode String is more than a single interview problem — it is the template for every nested-context problem. The same push-on-open, pop-on-close pattern powers Basic Calculator (#224), Number of Atoms (#726), Brace Expansion (#1087), and any problem where brackets define scope.

The core lesson is that stacks are the right tool whenever you need to save state before entering a nested scope and restore it when you exit. This is exactly how function call stacks work in programming languages — each function call pushes a frame, each return pops it. Understanding Decode String means understanding recursion itself, implemented iteratively.

The time complexity is O(n * max_expansion) where n is the length of the input string and max_expansion accounts for the repeated string building. The space complexity is O(n) for the stacks in the worst case with deeply nested brackets.

Practice this pattern with YeetCode flashcards to build instant recall. When you see brackets and repetition counts in an interview problem, the two-stack approach should be your automatic first instinct — not something you derive from scratch under pressure.