Decode String

Expand a string where k[text] means "repeat text k times", with brackets nested to any depth. A standard exercise in using a stack to handle nesting. Solve it below in Python or JavaScript, then read the walkthrough.

MediumString Stack Recursion Asked at 132 companies incl. Google, Amazon, Meta

Problem

You're given an encoded string s. The pattern k[text] stands for text written out k times in a row, where k is a positive integer. Patterns can be nested inside each other, and plain letters can appear anywhere outside or inside brackets.

Return the fully decoded string.

The input is always well formed: brackets are balanced, every [ is directly preceded by a number, and digits only ever appear as repeat counts (the decoded text itself contains only lowercase letters).

Example 1

Input: s = "2[xy]z"
Output: "xyxyz"

Example 2

Input: s = "3[m2[n]]"
Output: "mnnmnnmnn"

The inner 2[n] becomes "nn", so the outer pattern repeats "mnn" three times.

Example 3

Input: s = "ab4[c]d"
Output: "abccccd"

Letters outside any brackets are copied through unchanged.

Constraints

1 ≤ s.length ≤ 100
s contains lowercase English letters, digits, and the characters [ and ]
1 ≤ k ≤ 300
The decoded string has length ≤ 10⁵

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Decode String in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Decode String

Pattern: Stack for nested structure

Nesting is the signal. When you hit a [, you have to put aside everything you've built so far, decode the inside, and then come back and attach the result. "Put aside and come back later, most recent first" is exactly what a stack does.

Keep two pieces of running state: the text built at the current depth, and the number currently being read. On [, push both onto a stack and start fresh. On ], pop the saved text and count, and set the current text to saved + current * count. Letters append to the current text, and digits extend the current number (num = num * 10 + digit) so multi-digit counts work.

Approach 1: Repeatedly expand the innermost bracket

Find a k[letters] group with no brackets inside, replace it with its expansion, and repeat until no brackets remain. Simple, but every pass rebuilds the whole string, so deep nesting with long output does a lot of copying.

Time O(d · L), d = depth, L = output length · Space O(L)

Approach 2: Recursive descent

Write a function that decodes from an index until it hits ] or the end, returning the text and the index where it stopped. On a number followed by [, recurse for the inside, then repeat the result. Clean and linear, but the call stack mirrors the nesting depth.

Time O(L) · Space O(L)

Approach 3: One pass with an explicit stack

Scan left to right with current = "" and num = 0:

Digit: num = num * 10 + digit.
[: push (current, num), then reset both.
]: pop (prev, count) and set current = prev + current * count.
Letter: append it to current.

At the end, current is the answer. Building pieces in a list and joining them avoids quadratic string concatenation in languages where strings are immutable.

Time O(L) · Space O(L)

Approach	Time	Space
Repeatedly expand the innermost bracket	O(d · L), d = depth, L = output length	O(L)
Recursive descent	O(L)	O(L)
One pass with an explicit stack	O(L)	O(L)

Solution code

Try the practice editor first. Both solutions pass every test above.

Decode String solution in Python

def decode_string(s: str) -> str:
    stack = []  # (text before the bracket, repeat count)
    current = []
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            stack.append(("".join(current), num))
            current = []
            num = 0
        elif ch == "]":
            prev, count = stack.pop()
            current = [prev, "".join(current) * count]
        else:
            current.append(ch)
    return "".join(current)

Decode String solution in JavaScript

function decodeString(s) {
  const stack = []; // [text before the bracket, repeat count]
  let current = '';
  let num = 0;
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + Number(ch);
    } else if (ch === '[') {
      stack.push([current, num]);
      current = '';
      num = 0;
    } else if (ch === ']') {
      const [prev, count] = stack.pop();
      current = prev + current.repeat(count);
    } else {
      current += ch;
    }
  }
  return current;
}

Common mistakes

Treating each digit as a whole count, so "10[a]" is read as 0 copies (or 1) instead of 10.
Forgetting to reset the number after pushing it on "[", so the next count starts with leftover digits.
Dropping the text that came before the bracket. On "]" the result is the saved prefix plus the repeated text, not just the repeated text.
Assuming brackets only nest one level deep.

What interviewers look for

Point out the nesting first and say why it calls for a stack: each [ opens a context you have to return to after the matching ]. Then name exactly what goes on the stack (the prefix built so far and the repeat count). Interviewers listen for that, because pushing the wrong state is where most bugs come from.

Trace a nested case like "3[m2[n]]" on the whiteboard, showing the stack after each bracket. It also catches the multi-digit and reset bugs before you run anything.

Follow-up questions

What if the decoded output could be too large to fit in memory?

Produce it lazily. Parse the input into a tree of (count, children) nodes and write a generator that yields characters by walking the tree, repeating each subtree count times. You can also answer "what is the k-th character" without expanding, by computing each subtree’s decoded length and skipping whole repetitions.

How would you validate malformed input, such as unbalanced brackets?

Track the stack depth. A "]" with an empty stack, a "[" not preceded by digits, or a non-empty stack at the end all mean the input is invalid, and you can report the index where it failed.

Companies that ask Decode String

Decode String is tagged by 132 companies in our interview dataset. The score shows how often it comes up at each company.

and 108 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Decode String

MediumString Stack Recursion Asked at 132 companies incl. Google, Amazon, Meta

Problem

Return the fully decoded string.

Example 1

Input: s = "2[xy]z"
Output: "xyxyz"

Example 2

Input: s = "3[m2[n]]"
Output: "mnnmnnmnn"

The inner 2[n] becomes "nn", so the outer pattern repeats "mnn" three times.

Example 3

Input: s = "ab4[c]d"
Output: "abccccd"

Letters outside any brackets are copied through unchanged.

Constraints

1 ≤ s.length ≤ 100
s contains lowercase English letters, digits, and the characters [ and ]
1 ≤ k ≤ 300
The decoded string has length ≤ 10⁵

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Decode String in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Decode String

Pattern: Stack for nested structure

Approach 1: Repeatedly expand the innermost bracket

Time O(d · L), d = depth, L = output length · Space O(L)

Approach 2: Recursive descent

Time O(L) · Space O(L)

Approach 3: One pass with an explicit stack

Scan left to right with current = "" and num = 0:

Digit: num = num * 10 + digit.
[: push (current, num), then reset both.
]: pop (prev, count) and set current = prev + current * count.
Letter: append it to current.

At the end, current is the answer. Building pieces in a list and joining them avoids quadratic string concatenation in languages where strings are immutable.

Time O(L) · Space O(L)

Approach	Time	Space
Repeatedly expand the innermost bracket	O(d · L), d = depth, L = output length	O(L)
Recursive descent	O(L)	O(L)
One pass with an explicit stack	O(L)	O(L)

Solution code

Try the practice editor first. Both solutions pass every test above.

Decode String solution in Python

def decode_string(s: str) -> str:
    stack = []  # (text before the bracket, repeat count)
    current = []
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            stack.append(("".join(current), num))
            current = []
            num = 0
        elif ch == "]":
            prev, count = stack.pop()
            current = [prev, "".join(current) * count]
        else:
            current.append(ch)
    return "".join(current)

Decode String solution in JavaScript

function decodeString(s) {
  const stack = []; // [text before the bracket, repeat count]
  let current = '';
  let num = 0;
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + Number(ch);
    } else if (ch === '[') {
      stack.push([current, num]);
      current = '';
      num = 0;
    } else if (ch === ']') {
      const [prev, count] = stack.pop();
      current = prev + current.repeat(count);
    } else {
      current += ch;
    }
  }
  return current;
}

Common mistakes

Treating each digit as a whole count, so "10[a]" is read as 0 copies (or 1) instead of 10.
Forgetting to reset the number after pushing it on "[", so the next count starts with leftover digits.
Dropping the text that came before the bracket. On "]" the result is the saved prefix plus the repeated text, not just the repeated text.
Assuming brackets only nest one level deep.

What interviewers look for

Trace a nested case like "3[m2[n]]" on the whiteboard, showing the stack after each bracket. It also catches the multi-digit and reset bugs before you run anything.

Follow-up questions

What if the decoded output could be too large to fit in memory?

How would you validate malformed input, such as unbalanced brackets?

Track the stack depth. A "]" with an empty stack, a "[" not preceded by digits, or a non-empty stack at the end all mean the input is invalid, and you can report the index where it failed.

Companies that ask Decode String

Decode String is tagged by 132 companies in our interview dataset. The score shows how often it comes up at each company.

and 108 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Decode String

Approach 1: Repeatedly expand the innermost bracket

Approach 2: Recursive descent

Approach 3: One pass with an explicit stack

Solution code

Common mistakes

What interviewers look for

Follow-up questions

What if the decoded output could be too large to fit in memory?

How would you validate malformed input, such as unbalanced brackets?

Companies that ask Decode String

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Decode String

Approach 1: Repeatedly expand the innermost bracket

Approach 2: Recursive descent

Approach 3: One pass with an explicit stack

Solution code

Common mistakes

What interviewers look for

Follow-up questions

What if the decoded output could be too large to fit in memory?

How would you validate malformed input, such as unbalanced brackets?

Companies that ask Decode String

Practice next

Get live help in the real interview