← DSA Atlas
Dedicated problem page · #394

Decode String

MediumStack and Expression ProcessingNested-context stackStack
Solve on LeetCode ↗
394
MediumStack and Expression ProcessingStackNested-context stack

Decode String

Given an encoded string where the encoding rule is k[encoded_string], meaning the encoded_string inside the brackets is repeated exactly k times, return the fully decoded string. Brackets may be nested, k is a positive integer, and the original data contains no digits (digits only appear as repeat counts).

Open official problem prompt ↗
In plain English

Expand a compressed, possibly nested run-length notation into the literal string it represents.

Picture it like this

Like opening nested Russian dolls: each time you open a bracket you set the current doll aside, work on the smaller one inside, then place the finished inner doll back into the one you set aside.

Example
Input
s = "3[a2[c]]"
Output
"accaccacc"
Why
The inner 2[c] expands to "cc", making "acc", and the outer 3[...] repeats "acc" three times.
Constraints
1 <= s.length <= 30s consists of lowercase English letters, digits, and square brackets '[]'s is guaranteed to be a valid inputAll integers are in the range [1, 300]The decoded string may be much longer than s
Pattern lesson

See the pattern, then code

Nested-context stack
Recognition clue

Repetition with nested brackets means an inner context must be fully resolved before its enclosing context finishes — that last-opened-first-closed nesting is the signal for a stack.

↗
Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. When you hit '[' you must pause the string you were building and its pending multiplier, dive into the inner group, then on ']' pop back and splice the repeated inner result onto the paused outer string.

New words, made simpleKnow these before the algorithm
Nested encoding
A repeated group that itself contains another repeated group, e.g. 3[a2[c]].
Current context
The string being built at the current bracket depth, plus the multiplier waiting to be applied to it.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Recursive descent

Correct and clean, but recursion depth risk and index bookkeeping make it error-prone under interview pressure.

Recurse on each bracketed segment, returning the expanded substring to the caller.

Time O(N) in output sizeSpace O(depth) call stack
Best choiceTwo-stack iterative expansion

Single linear pass, no recursion, and each bracket maps to one push/pop — the interview-standard solution.

Keep a stack of paused strings and a stack of paused counts; on ']' pop and splice the repeated inner result.

Time O(N) in output sizeSpace O(N)
The rule we keep true

Invariant

At every moment, cur holds the fully decoded text for the current bracket depth, and the stacks hold exactly the paused outer strings and their pending multipliers.

Why this is correct

Reasoning

Each '[' saves the enclosing state and starts a fresh inner build; each ']' reconstructs the enclosing state by multiplying the completed inner build. Because brackets nest properly, pushes and pops pair up, so every group is multiplied by exactly the right factor exactly once.

The algorithm in three movesSay these aloud before coding
1Accumulate multi-digit numbers as you read digit characters

numStack=[3,2] strStack=["","a"] cur="c"

2On '[', push the current built string and current count, then reset both

after inner ']': cur="acc"

3On ']', pop the previous string and count, and append current * count to it

after outer ']': cur="accaccacc"

4On a letter, append it to the current built string

5Return the final built string after the scan

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
[1
a2
23
[4
c5
]6
]7
1 · Read'3'
2 · AskDigit?
3 · Update statenum=3, cur=""
4 · ResultAccumulate the count
Key takeaway

The inner group 2[c] is being resolved before the outer 3[...] completes.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 7-8Build multi-digit counts

    num*10+digit handles counts like 12 or 300 that span several characters.

  2. 2
    Lines 9-14Open bracket saves state

    Push the pending count and the outer string, then reset so the inner group builds cleanly.

  3. 3
    Lines 15-18Close bracket splices back

    Pop the count and outer prefix, and append cur repeated k times to reconstruct the enclosing context.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single group with no nesting, e.g. "3[a]"
  • Multi-digit counts, e.g. "10[a]"
  • Deeply nested groups, e.g. "2[2[2[a]]]"
  • Leading/trailing plain letters outside any bracket, e.g. "ab3[cd]ef"
!

Common beginner mistakes

  • Treating each digit as a separate count instead of accumulating multi-digit numbers
  • Applying the multiplier at '[' instead of at ']' when the inner build is complete
  • Forgetting to reset num and cur after pushing on '['
  • Using string concatenation inside a tight recursive loop and mishandling the return position
Check your understanding

Why must the repeat count be applied when reading ']' rather than when reading '['?

More in Stack and Expression Processing

#20Valid ParenthesesMatching stack for bracket pairs#71Simplify PathStack of path components#150Evaluate Reverse Polish NotationOperand stack for postfix evaluation#155Min StackStack augmented with running minimum#224Basic CalculatorStack for parenthesized sign context#227Basic Calculator IIStack with deferred multiply/divide