Decode String [Medium] — Stack-Based Expansion

Problem Statement

Decode an encoded string where k[encoded_string] means encoded_string repeated k times. Brackets can be nested.

"3[a]2[bc]"   → "aaabcbc"
"3[a2[c]]"    → "accaccacc"
"2[abc]3[cd]ef" → "abcabccdcdcdef"

Intuition

Use a stack of (count, built_string) pairs. When we see [, push; when we see ], pop and repeat. Collect digits into a running number.

Solutions

C++

string decodeString(string s) {
    stack<pair<int,string>> stk;
    string cur; int num = 0;
    for (char c : s) {
        if (isdigit(c)) { num = num*10 + (c-'0'); }
        else if (c == '[') { stk.push({num, cur}); cur=""; num=0; }
        else if (c == ']') {
            auto [k, prev] = stk.top(); stk.pop();
            for (int i=0;i<k;i++) prev+=cur;
            cur = prev;
        } else cur += c;
    }
    return cur;
}

Java

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

JavaScript

var decodeString = function(s) {
    const stack = [];
    let cur = '', num = 0;
    for (const c of s) {
        if (c >= '0' && c <= '9') num = num*10 + +c;
        else if (c === '[') { stack.push([num, cur]); cur=''; num=0; }
        else if (c === ']') {
            const [k, prev] = stack.pop();
            cur = prev + cur.repeat(k);
        } else cur += c;
    }
    return cur;
};

Python

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

Complexity

Time: O(n × max_k) — output length drives time
Space: O(n) stack depth