Decode String
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
Given an encoded string, decode it. The encoding rule is k[encoded_string], meaning the encoded_string inside the brackets is repeated exactly k times. k is always a positive integer. You may assume the input is always valid with well-formed brackets and no extra whitespace.
Example 1
- Input
- s = "2[x]3[yz]"
- Output
- "xxyzyzyz"
- Why
- "x" twice, then "yz" three times.
Example 2
- Input
- s = "2[m3[n]]"
- Output
- "mnnnmnnn"
- Why
- Inside first: 3[n] is "nnn", so the block is "mnnn", written twice.
Example 3
- Input
- s = "3[ab]2[q]z"
- Output
- "abababqqz"
- Why
- "ab" three times, "q" twice, then the plain "z".
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]
How to think about it
Updated 2026-09-29Brackets denote nested scopes. When an opening bracket arrives, current string assembly must freeze and wait for the inner sub-problem to resolve. Pushing the multiplier and the prefix built so far onto a stack suspends the outer scope; when the matching closing bracket appears, popping them resumes the outer scope and multiplies the freshly completed inner chunk.
Approaches, worst first
Recursive inner bracket expansion
time O(maxK * n^2) · space O(maxK * n)
Scan for the innermost `[` and its corresponding `]`, duplicate the enclosed substring k times, replace the bracketed expression in the string, and repeat until no brackets remain. Constructing and slicing new strings on every replacement incurs substantial reallocation overhead.
Two stacks for counts and stringsWrite this one
time O(output.length) · space O(output.length)
Iterate through characters. Accumulate digits into a multi-digit integer k, and plain characters into a current string buffer. On `[`, push k and the current string onto stacks, then reset both. On `]`, pop the repetition count and previous string, then update `current = prev + current * count`.
Where people lose marks · 3
- Assuming multipliers are single digits: counts can range up to 300, so digits must be accumulated via `k = k * 10 + digit` across consecutive numeric characters.
- Letters occurring outside or between bracket blocks (e.g. `2[a]bc3[d]`) must append directly to the running string buffer rather than requiring bracket encapsulation.
- Failing to reset the current number accumulator to 0 upon pushing it on `[` corrupts subsequent multipliers.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .