Decode String

Approach Summary

Use stack to track (current_string, repeat_count). On ], pop and repeat the current segment.

Full Solution & Approach

Nested repetition like 3[a2[c]] requires tracking two pieces of state as you scan: the string built so far at the current nesting level and the repeat count that governs it. Use a stack of (previous_string, repeat_count) pairs. On a digit, accumulate the full number (digits can be multi-character). On an opening bracket, push the current string and number onto the stack and reset both. On a closing bracket, pop the pair, repeat the current string count times, and append it to the popped previous string — this reconstructs the inner level and splices it into the outer one. Ordinary letters are appended to the current string. Each character is processed once, and each push/pop is O(1), though the output itself can be exponential in the nesting depth, which bounds the total work.

Each character is scanned once and each stack operation is O(1) — but the decoded output can be exponential, so the worst case is O(final output length). The stack holds one pair per nesting level — O(depth).

Solution Code

Solution

def decode_string(s: str) -> str:
    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

function decodeString(s) {
  const stack = [];
  let cur = '';
  let num = 0;
  for (const ch of s) {
    if (/d/.test(ch)) num = num * 10 + Number(ch);
    else if (ch === '[') {
      stack.push([cur, num]);
      cur = ''; num = 0;
    } else if (ch === ']') {
      const [prev, k] = stack.pop();
      cur = prev + cur.repeat(k);
    } else cur += ch;
  }
  return cur;
}

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

string decodeString(const string& s) {
    vector<string> strStack;
    vector<int> numStack;
    string cur;
    int num = 0;
    for (char ch : s) {
        if (isdigit(ch)) {
            num = num * 10 + (ch - '0');
        } else if (ch == '[') {
            strStack.push_back(cur);
            numStack.push_back(num);
            cur = "";
            num = 0;
        } else if (ch == ']') {
            string prev = strStack.back(); strStack.pop_back();
            int k = numStack.back(); numStack.pop_back();
            string segment = cur;
            for (int i = 1; i < k; i++) cur += segment;
            cur = prev + cur;
        } else {
            cur += ch;
        }
    }
    return cur;
}

Edge Cases to Watch

Multi-digit repeat counts like 10[a]
Deeply nested patterns like 3[a2[b1[c]]]
Letters before any bracket — appended normally
Empty encoded string

How to Recognize This Pattern

Nested repeated patterns
k[encoded_string]

Complexity Analysis

Time Complexity

O(n · k)

Space Complexity

O(n)