Problem statement

Given an encoded string, return its decoded form. The rule k[encoded_string] means the bracket content is repeated exactly k times. The input is always valid; digits appear only 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
• 1 <= k <= 3
• Nesting depth <= 2; output length <= 300.

Hints for Decode String

1. Hint 1

   Keep two stacks: repeat counts and the string built so far, pushed at every '['.

2. Hint 2

   On ']', pop both and append the repeated inner string to the restored outer one.

How to solve Decode String

k[...] nests, so this is naturally recursive. You can make it iterative by keeping the recursion's saved state yourself: at every [ park the work-in-progress string and the count that is about to apply, then start a fresh string for the inside. At the matching ] the inner string is finished, so multiply it and glue it back onto what you parked.

Approach

1. Track cur, the string being built at the current depth, and num, the count being read.
2. On a digit, extend the number with num = num * 10 + digit — counts can have more than one digit.
3. On [, push num onto the count stack and cur onto the string stack, then reset both to empty. Everything from here belongs to the inner level.
4. On ], pop the repeat count and the parked prefix, and set cur = prefix + cur * repeat. The inner level is done and folded into its parent.
5. On a letter, append it to cur. When the scan ends, cur is the decoded string.

Why it works

The two stacks are the call stack of the recursive version, written out by hand. At a [ everything to the left at that depth is complete and can be set aside; at the matching ] the bracket's content is complete and its multiplier is known, so the expansion can be performed and handed back to the enclosing level. Since brackets are properly nested, pushes and pops pair up exactly, and each level is resolved innermost-first.

Complexity

• Time — O(total length of the decoded output)
• Space — O(total length of the decoded output)

Pitfalls

• Reset both num and cur at [. Forgetting cur leaks the outer text into the repeated section.
• The popped string is the prefix: it goes before the repeated part, so prefix + cur * repeat, never the other way round.
• Accumulate multi-digit counts with num * 10 + digit; reading one character as the whole number breaks on counts of 10 or more.

Reference solution

Python

def decodeString(s: str) -> str:
    count_st = []
    str_st = []
    cur = ""
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            count_st.append(num)
            str_st.append(cur)
            num = 0
            cur = ""
        elif ch == "]":
            repeat = count_st.pop()
            cur = str_st.pop() + cur * repeat
        else:
            cur += ch
    return cur

Java

public static String decodeString(String s) {
    Deque<Integer> countSt = new ArrayDeque<>();
    Deque<String> strSt = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int num = 0;
    for (char ch : s.toCharArray()) {
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + (ch - '0');
        } else if (ch == '[') {
            countSt.push(num);
            strSt.push(cur.toString());
            num = 0;
            cur = new StringBuilder();
        } else if (ch == ']') {
            int repeat = countSt.pop();
            StringBuilder rep = new StringBuilder(strSt.pop());
            for (int r = 0; r < repeat; r++) rep.append(cur);
            cur = rep;
        } else {
            cur.append(ch);
        }
    }
    return cur.toString();
}

C++

string decodeString(string s) {
    vector<int> countSt;
    vector<string> strSt;
    string cur;
    int num = 0;
    for (char ch : s) {
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + (ch - '0');
        } else if (ch == '[') {
            countSt.push_back(num);
            strSt.push_back(cur);
            num = 0;
            cur.clear();
        } else if (ch == ']') {
            int repeat = countSt.back();
            countSt.pop_back();
            string prefix = strSt.back();
            strSt.pop_back();
            string rep;
            for (int r = 0; r < repeat; r++) rep += cur;
            cur = prefix + rep;
        } else {
            cur += ch;
        }
    }
    return cur;
}

JavaScript

var decodeString = function(s) {
    const countSt = [];
    const strSt = [];
    let cur = "", num = 0;
    for (const ch of s) {
        if (ch >= "0" && ch <= "9") {
            num = num * 10 + (ch.charCodeAt(0) - 48);
        } else if (ch === "[") {
            countSt.push(num);
            strSt.push(cur);
            num = 0;
            cur = "";
        } else if (ch === "]") {
            const repeat = countSt.pop();
            cur = strSt.pop() + cur.repeat(repeat);
        } else {
            cur += ch;
        }
    }
    return cur;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium