Decode String

mediumAmazon-tagged: Mixed71 stepsJava · Python · C++

Decode strings like "3[a2[c]]" into "accaccacc". Use two stacks: on '[', push the current repeat count and the text built so far, then start fresh. On ']', pop them and append the inner text repeated that many times.

▶ Watch the animated trace

Traced input: s = "3[a2[c]]" → "accaccacc". Original problem: neetcode.io/problems/decode-string

Complexity

BestO(n)

AverageO(output)

WorstO(output)

SpaceO(n)

The output can be much longer than the input.

Key idea

Brackets nest, so the innermost group must finish first: a stack.
Numbers can have several digits: k = k * 10 + digit.
On ']', the text built inside the brackets is repeated and attached to the outer text.

Common mistakes

Assuming single-digit counts.
String concatenation in loops is slow; use StringBuilder.

Solution

Java

String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> texts = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            counts.push(k);
            texts.push(cur);
            cur = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            StringBuilder outer = texts.pop();
            int times = counts.pop();
            for (int t = 0; t < times; t++) outer.append(cur);
            cur = outer;
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

Python

def decodeString(s: str) -> str:
    stack, cur, k = [], "", 0
    for c in s:
        if c.isdigit():
            k = k * 10 + int(c)
        elif c == '[':
            stack.append((cur, k))
            cur, k = "", 0
        elif c == ']':
            outer, times = stack.pop()
            cur = outer + cur * times
        else:
            cur += c
    return cur

C++

string decodeString(string s) {
    stack<pair<string, int>> st;
    string cur;
    int k = 0;
    for (char c : s) {
        if (isdigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            st.push({cur, k});
            cur.clear();
            k = 0;
        } else if (c == ']') {
            auto [outer, times] = st.top(); st.pop();
            for (int t = 0; t < times; t++) outer += cur;
            cur = outer;
        } else {
            cur += c;
        }
    }
    return cur;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Adjacent groups Each group is decoded independently.	`s = "2[abc]3[cd]ef"`	`"abcabccdcdcdef"`
Multi-digit count The count is read digit by digit.	`s = "10[a]"`	`"aaaaaaaaaa"`
No brackets Plain text passes through.	`s = "abc"`	`"abc"`