MediumStringStackRecursionUpdated Sep 2026

394. Decode String

Asked at TikTok

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

String

Companies

1

Problem

You are given an encoded string. Your job is to return the decoded string it stands for.

The encoding uses the pattern k[encoded_string]. This means the text inside the square brackets is repeated exactly k times. Here k is always a positive whole number. Brackets can be nested, so the inside part may itself contain more k[...] groups. For example, 3[a2[c]] means: build a plus c twice, then repeat that whole thing three times.

Letters that sit outside any brackets are just copied to the output as they are. You can assume the input is always valid: brackets are balanced, there are no spaces, and digits only appear as repeat counts (never as normal text). The final decoded string will never be longer than 10^5 characters.

Nested groups must be expanded inside-out

sinner: 2[c]outer: 3[...]3[a2[c]]01234567The inner bracket pair must be resolved before the outer one.
The inner `2[c]` is expanded first, then the outer `3[...]` repeats the whole result.

Constraints

  • ●1 <= s.length <= 30
  • ●s consists of lowercase English letters, digits, and square brackets '[]'
  • ●s is guaranteed to be a valid input
  • ●All the integers in s are in the range [1, 300]

Examples

Example 1
Inputs = "3[a]2[bc]"
Output"aaabcbc"
Why`3[a]` gives `aaa`, and `2[bc]` gives `bcbc`. Put them together and you get `aaa` + `bcbc` = `aaabcbc`.
Example 2
Inputs = "3[a2[c]]"
Output"accaccacc"
WhyThe inner `2[c]` becomes `cc`, so the inside of the outer group is `a` + `cc` = `acc`. Repeating that three times gives `accaccacc`.
Example 3
Inputs = "2[abc]3[cd]ef"
Output"abcabccdcdcdef"
Why`2[abc]` is `abcabc`, `3[cd]` is `cdcdcd`, and the trailing `ef` is copied as is. Joining them gives `abcabc` + `cdcdcd` + `ef`.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Nesting means you cannot expand left to right in one flat pass — when you see ] you need to know which multiplier and which prefix it belongs to.

2

Key insight: use a stack of (prefix, multiplier) pairs. When you see [, push the string built so far and the number just read, then start a fresh current string. When you see ], pop and set current = prefix + current * multiplier.

3

Multipliers can have several digits ("12[a]"), so accumulate digits as num = num * 10 + digit and reset num after pushing.

4

Walkthrough for "3[a2[c]]": 3 -> num=3. [ push ("",3), cur="". a -> cur="a". 2 -> num=2. [ push ("a",2), cur="". c -> cur="c". ] pop ("a",2) -> cur="acc". ] pop ("",3) -> cur="accaccacc".

5

Letters outside any brackets are simply appended to the current string.

Optimal Approach

Step 1: stack = [], cur = "", num = 0.
Step 2: For each char ch:
If digit: num = num * 10 + int(ch).
If [: push (cur, num); reset cur = "", num = 0.
If ]: pop (prev, k); cur = prev + cur * k.
Otherwise (letter): cur += ch.
Step 3: Return cur.

Time: O(output length). Space: O(output length) including the stack.

Stack of (prefix, multiplier) pairs

stack("", 3)← topAfter reading `3[`: push the empty prefix and thecount 3, then start a fresh current string.stack("", 3)("a", 2)← topAfter reading `a2[`: push prefix `a` with count 2,then reset current to empty.stack("", 3)← topOn the first `]`: pop `("a", 2)` and set current = `a`+ `c`*2 = `acc`.on '[': push (cur, num)on ']': cur = prev + cur * klast ']' → "" + "acc"*3 = accaccacc
On `[` we save the prefix and count; on `]` we pop them and glue the repeated part back on.
ComplexityTime O(n)Space O(n)n is the length of the decoded output; the cost comes from building every output character once and keeping the stack of open groups.

What Trips People Up in Real Interviews

1

Assuming single-digit multipliers. "10[a]" must produce ten as — accumulate digits.

2

Forgetting to save the prefix before [. Without it, text before a nested block like the a in "2[a3[b]]" is lost.

3

Not resetting num after pushing it, so digits from the outer number leak into the inner one.

4

Using string concatenation in a tight loop in Java without a StringBuilder — it works but is slow for long outputs.

Solution Code

O(n) time
def decodeString(s):
    stack = []
    cur = ''
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == '[':
            stack.append((cur, num))
            cur, num = '', 0
        elif ch == ']':
            prev, k = stack.pop()
            cur = prev + cur * k
        else:
            cur += ch
    return cur

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Decode String problem?

Decode String expands an encoded string where `k[encoded]` means the inside repeated `k` times, and encodings can be nested — `"3[a2[c]]"` becomes `"accaccacc"`. It tests whether you can manage nested state cleanly with a stack (or recursion).

How do you solve Decode String?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Decode String?

Decode String is asked at TikTok. It is a medium difficulty problem.

What are common mistakes on Decode String?
  • Assuming single-digit multipliers. `"10[a]"` must produce ten `a`s — accumulate digits.
  • Forgetting to save the prefix before `[`. Without it, text before a nested block like the `a` in `"2[a3[b]]"` is lost.
  • Not resetting `num` after pushing it, so digits from the outer number leak into the inner one.
  • Using string concatenation in a tight loop in Java without a `StringBuilder` — it works but is slow for long outputs.