Problem 9.4 · Stack and Monotonic StackMedium

Decode String

What it teaches: Stacks of saved state: on '[' save what you've built and the repeat count; on ']' pop and combine.

Practise it on judges as “Decode String”.

The problem

Decode a string where k[text] means text repeated k times. Brackets can nest. Digits only appear as repeat counts.

Example 1

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2

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

Example 3

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints

1 ≤ s.length ≤ 30
Counts are 1 to 300
The decoded length ≤ 10⁵

Pattern clues in the wording

→ Nested brackets with an action at the closing bracket
→ The innermost part is resolved first

These clues point to Stack for Matching and Undo: Push openers and pop when the matching closer arrives; anything left over or mismatched is an error.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public String decodeString(String s) {
        return "";
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "3[a]2[bc]"	"aaabcbc"
2	s = "3[a2[c]]"	"accaccacc"
3	s = "2[abc]3[cd]ef"	"abcabccdcdcdef"

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: two stacks (counts and partial strings) · O(output length)

Optimal: two stacks (counts and partial strings)

Time O(output length) Space O(output length)

Build the current string in a StringBuilder and read numbers digit by digit. On '[', push the count and the current builder, then start fresh. On ']', pop the count and the previous builder, and append the current string that many times to it.

▶ Dry run: Decoding 3[a2[c]]s = "3[a2[c]]"

[

↑i

[

]

counts(stack)

saved strings(stack)

current(vars)

Step 1/4Read 3, then '[': save count 3 and the empty string; start fresh.

Approach 1

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String decodeString(String s) {
        Deque<Integer> counts = new ArrayDeque<>();
        Deque<StringBuilder> saved = new ArrayDeque<>();
        StringBuilder cur = new StringBuilder();
        int k = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                counts.push(k);
                saved.push(cur);
                cur = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                StringBuilder prev = saved.pop();
                prev.append(cur.toString().repeat(counts.pop()));
                cur = prev;
            } else {
                cur.append(c);
            }
        }
        return cur.toString();
    }
}

Verdict: Each character of the output is written a bounded number of times.

Before you submit

Edge cases and common mistakes

Test these inputs

Multi-digit counts like 10[a]
Letters after the last bracket
Deep nesting

Mistakes people make

Reading counts one digit at a time without accumulating (10 becomes 1 and 0).
Forgetting to reset the count after '['.

Interview

Follow-up questions

Could you solve it recursively?

Command Palette

The problem

Approaches

Optimal: two stacks (counts and partial strings)

Edge cases and common mistakes

Follow-up questions

Related problems