Community Problem

Decode String

Difficulty: Medium

Expand a run-length-encoded string with arbitrary nesting using two parallel stacks (counts and string fragments).

Decode String

Expand a run-length-encoded string with arbitrary nesting using two parallel stacks (counts and string fragments).

MEDIUM

Free

stack

strings

recursion

By CodeSnatch

April 5, 2026

Updated May 18, 2026

667 views

4.6 (12)

This came up on a Tier-1 onsite the week I was prepping for my staff transition, and the misstep I see candidates make is reaching for regex and getting buried by the nested case. The two-stack pattern is the canonical solve and is the same shape that powers basic-calculator and nested-list problems.

Decode String

Given an encoded string s, return its decoded form. The encoding rule is k[encoded_string], where encoded_string inside the brackets is repeated exactly k times. k is a positive integer (one or more digits). The input is guaranteed to be a well-formed encoded string with brackets balanced and k always immediately followed by '['. There are no extra spaces. The encoded string may contain digits inside encoded_string only as part of nested counts (e.g. "3[a2[c]]"), never as raw payload.

Examples

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Explanation: "3[a]" becomes "aaa", "2[bc]" becomes "bcbc", concatenated.

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: Inner "2[c]" is "cc". Then "3[acc]" is "accaccacc".

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Explanation: "abcabc" plus "cdcdcd" plus literal "ef".

Example 4:

Input: s = "abc"
Output: "abc"
Explanation: No brackets, the string is its own decoding.

Constraints

1 <= s.length <= 30
s consists of lowercase English letters, digits, '[', and ']'.
s is guaranteed to be a valid input that produces a string of length at most 10^4.
The integer k satisfies 1 <= k <= 300.

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach

This is a parsing problem with arbitrary nesting depth, which immediately suggests a stack. The trick is that you have two pieces of state to remember when entering a bracket: the repetition count k AND the partial string built up so far at the outer level. Use two parallel stacks.

Key insight

When you encounter '[', you are about to start a NEW context for the inner string. Save (push) both the count k you just parsed and the outer-level partial buffer, then reset both. When you encounter ']', you finish the inner buffer; pop the saved count and outer buffer, and stitch them: outer + inner.repeat(count). That stitched value becomes your new "current" buffer at the outer level. The recursion is encoded entirely in the stacks; you never need an explicit recursive call.

Algorithm

Initialize countStack = [], stringStack = [], current = "", k = 0.
For each character ch:
- Digit: k = k * 10 + (ch - '0') (handles multi-digit counts).
- '[': push k onto countStack, push current onto stringStack, reset k = 0 and current = "".
- ']': pop repeat = countStack.pop() and previous = stringStack.pop(), then set current = previous + current.repeat(repeat).
- Letter: current += ch.
Return current after the scan.

Complexity

Text

Metric  Value
------  ---------
Time    O(N) where N is the size of the DECODED output
Space   O(D + N) where D is the maximum nesting depth

We touch every character of the decoded output a constant number of times (the repeat op writes each output char once into current). The stack depth tracks the nesting depth.

Why it works

The grammar is S -> (digits '[' S ']' | letter)*. A stack with one frame per active '[' exactly matches the grammar's nesting structure, and the outer-buffer slot lets us splice the inner expansion into the right place when we close the bracket. Because we push BEFORE resetting and pop AFTER stitching, every '[' matches the right ']' and the outer context is preserved.

Pitfalls

Forgetting that k can be multi-digit. k = k * 10 + digit is the standard idiom.
Resetting current BEFORE pushing it. Push first, then reset.
Trying to use a single stack of mixed types. The two-stack version is cleaner.
Building the result with current = current + current style updates has wrong semantics; use previous + current.repeat(k) only when popping.

Solution Code

All Problems