Decode String

Table of Contents +

Decode String is where interviewers see if you really understand a stack. The input has a number, then a bracket, then text to repeat. And those can be nested inside each other. So a simple loop is not enough. You need a structure that remembers where you were before you went deeper. That structure is a stack.

🎯 The Problem

You get an encoded string and you expand its repeat patterns back into plain text.

A number k then [text] means repeat that text k times. So "3[a]" is "aaa".
Brackets can be nested. A pattern can sit inside another pattern.
The input is always valid. Brackets always match. Numbers are positive.

For "3[a2[c]]": the inner 2[c] is "cc". Inside the outer bracket we get "a" plus "cc", which is "acc". The outer 3[...] repeats that three times. The answer is "accaccacc".

Input:  s = "3[a2[c]]"
Output: "accaccacc"

Explanation:
  2[c]      -> "cc"
  a + "cc"  -> "acc"
  3[acc]    -> "accaccacc"

The hard part is the nesting. When you open a new bracket, you must pause your current work and start fresh inside. A stack is the tool for that. A stack is a pile where you add to the top and remove from the top, so the last thing in is the first thing out.

Here is the nested structure of "3[a2[c]]", showing how the inner bracket sits inside the outer one.

🐢 Approach 1: Recursion (Alternative)

The idea in one line: when you hit a bracket, call the function again to decode the inside.

The idea:

Recursion means a function that calls itself to handle a smaller piece.
On a [, recurse to decode the inner text. On ], return it up.

How it works:

Read the number, then recurse for the part inside the brackets.
Repeat the returned text that many times. Glue it onto the current text.

Why it is weak:

The inner call must report where it stopped, so the outer call can continue. That index tracking is easy to get wrong.
Deep nesting grows the call stack.
A plain loop with a stack does the same job with flat code.

Here is the recursive code for that idea:

def decode_string(s):
    def parse(i):
        result = []
        number = 0
        while i < len(s):
            ch = s[i]
            if ch.isdigit():
                number = number * 10 + int(ch)
            elif ch == "[":
                inner, i = parse(i + 1)
                result.append(inner * number)
                number = 0
            elif ch == "]":
                return "".join(result), i
            else:
                result.append(ch)
            i += 1
        return "".join(result), i

    decoded, _ = parse(0)
    return decoded

⚡ Approach 2: Two Stacks for Counts and Text (Best)

The idea in one line: keep one stack of paused counts and one stack of paused text, then resume them on each ].

The idea:

Walk the string one character at a time.
Hold a current number k and a current built string cur.
Keep two stacks. One for counts. One for paused text pieces.

How it works:

Digit: grow the number. k = k * 10 + digit, so multi-digit counts work.
[: push k and push cur, then reset k to zero and cur to empty for the inside.
]: pop repeat and pop prev, then set cur = prev + cur * repeat.
Letter: add it to cur.

Why it is fast:

Each character is handled once.
At the end cur holds the full answer.
The two stacks let us pause and resume across every level of nesting.

Steps to Solve

Make a count stack and a text stack. Set k to zero and cur to empty.
Walk the string one character at a time.
If the character is a digit, update k = k * 10 + digit.
If it is [, push k and cur, then reset k to zero and cur to empty.
If it is ], pop the count and the paused text, then set cur = prev + cur repeated count times.
If it is a letter, append it to cur.
After the whole string, cur is the decoded answer.

Here is how the two stacks fill and empty while reading "3[a2[c]]". The push happens on [ and the pop with repeat happens on ].

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses two lists as stacks, one for counts and one for paused text.

def decode_string(s):
    num_stack = []          # paused counts
    str_stack = []          # paused text pieces
    cur = ""
    k = 0

    for c in s:
        if c.isdigit():
            k = k * 10 + int(c)        # build multi-digit number
        elif c == "[":
            num_stack.append(k)        # pause the count
            str_stack.append(cur)      # pause the text
            k = 0
            cur = ""
        elif c == "]":
            repeat = num_stack.pop()   # how many times to repeat
            prev = str_stack.pop()     # text before this bracket
            cur = prev + cur * repeat  # glue repeated piece back on
        else:
            cur += c                   # a plain letter

    return cur


print(decode_string("3[a2[c]]"))

The output of the above code will be:

accaccacc

Let us trace the Python version line by line on "3[a2[c]]". We start with two empty stacks, cur empty, and k zero.

We read '3'. It is a digit, so k = 0 * 10 + 3 = 3.

We read '['. We push k, which is 3, onto the count stack. We push cur, which is empty, onto the text stack. Then we reset k to 0 and cur to empty. The count stack is now [3] and the text stack is [""].

We read 'a'. It is a letter, so cur becomes "a".

We read '2'. It is a digit, so k = 0 * 10 + 2 = 2.

We read '['. We push k, which is 2, and cur, which is "a". We reset k to 0 and cur to empty. Now the count stack is [3, 2] and the text stack is ["", "a"].

We read 'c'. cur becomes "c".

We read the first ']'. We pop repeat = 2 and prev = "a". Then cur = prev + cur * repeat = "a" + "c" * 2 = "acc". The stacks are back to [3] and [""].

We read the second ']'. We pop repeat = 3 and prev = "". Then cur = "" + "acc" * 3 = "accaccacc". The string is done, and cur holds the answer.

The line k = k * 10 + int(c) is what makes multi-digit numbers work, like 12[a]. The line cur = prev + cur * repeat is the heart of it. It repeats the finished inner piece and glues it onto the paused outer text.

⏱️ Time and Space Complexity

The time depends on the length of the decoded output, because we build every character of it. Call the output length N. The time is O(N). The two stacks hold the paused pieces, and at worst that is also about the size of the output. So the space is O(N) too. There is no way around building each output character at least once.

Approach	Time Complexity	Space Complexity
Recursion	O(N)	O(N)
Two stacks (counts and text)	O(N)	O(N)

Tip

Watch out for numbers with more than one digit. The line k = k * 10 + digit is what turns “12” into the number twelve instead of leaving it as a one and a two.

🧩 Key Takeaways

✅ Nested brackets need a stack, because you must pause the outer work and resume it later.
✅ Keep one stack for counts and one for paused text pieces.
✅ On ”[”, push the current count and text, then reset both for the inside.
✅ On ”]”, pop the count and the previous text, then set cur to prev plus cur repeated count times.
✅ Use k = k * 10 + digit so multi-digit numbers like 12 are read correctly.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Multiply Strings
Merge Strings Alternately

Previous Merge Strings Alternately Next Minimum Remove to Make Valid Parentheses

Decode String

Follow Us

Follow Us