Decode String

Overview

Decode string: given a string like "3[a]2[bc]", decode to "aaabcbc". Rules: digits (possibly multi-digit) form a repeat count k; "k[encoded_string]" means repeat the decoded inner string k times. Use two stacks: one for repeat counts, one for string segments (prefix before the current bracket). On '[', push count and current string, reset current. On ']', pop count and prefix, set current = prefix + current.repeat(count).

When to Use

• Nested encoded string — k[ ... ] with possible nesting.
• Expression with brackets — similar push/pop on brackets.
• Build string from nested structure — stack of (count, prefix) or recursion.

How It Works

Scan left to right. Accumulate digits into num. On '[', push (num, curr), reset num and curr. On ']', pop (repeat, prev), curr = prev + curr.repeat(repeat). On a letter, append to curr. Result is final curr.

Example 1: Two Stacks (Standard)

function decodeString(s: string): string {
  const countStack: number[] = [];
  const strStack: string[] = [];
  let curr = '';
  let num = 0;
  for (const c of s) {
    if (c >= '0' && c <= '9') num = num * 10 + Number(c);
    else if (c === '[') {
      countStack.push(num); num = 0;
      strStack.push(curr); curr = '';
    } else if (c === ']') {
      const repeat = countStack.pop()!;
      curr = strStack.pop()! + curr.repeat(repeat);
    } else curr += c;
  }
  return curr;
}

Time: O(maxK * output length). Space: O(n).

Example 2: Recursive (Helper for Bracket Segment)

When you see a digit, parse the number, then skip '[', recursively decode until the matching ']' (track balance), then repeat the result and append. Use a global or passed index to advance through the string.

function decodeStringRec(s: string): string {
  let i = 0;
  function decode(): string {
    let res = '';
    while (i < s.length && s[i] !== ']') {
      if (s[i] >= '0' && s[i] <= '9') {
        let num = 0;
        while (s[i] >= '0' && s[i] <= '9') num = num * 10 + Number(s[i++]);
        i++; // skip '['
        const inner = decode();
        i++; // skip ']'
        res += inner.repeat(num);
      } else res += s[i++];
    }
    return res;
  }
  return decode();
}

Example 3: Single Stack of (count, string) Pairs

Push a pair (count, segment) when you see '['; on ']' pop (k, prev), decode current segment and set current = prev + current.repeat(k). Alternatively, store (num, accumulatedString) so that when you pop, you have the repeat count and the prefix; current holds the inner part.

Example 4: Step-by-Step Trace

s = "3[a2[c]]". i=0: num=3. i=1: '[', push (3,""), curr="". i=2: curr="a". i=3: num=2. i=4: '[', push (2,"a"), curr="". i=5: curr="c". i=6: ']', pop 2,"a", curr="a"+"cc"="acc". i=7: ']', pop 3,"", curr=""+"accaccacc"="accaccacc". Result "accaccacc".

Example 5: Edge Cases

• No brackets: e.g. "abc" — curr builds to "abc"; return as-is.
• Single segment: "2[ab]" — push (2,""), curr="ab"; pop gives "" + "ab".repeat(2) = "abab".
• Multi-digit count: "10[a]" — num becomes 10; push 10; curr="a"; pop gives "a".repeat(10).
• Empty segment: "2[]" — curr="" inside; pop gives "".repeat(2) = "".

Summary

• Decode string: two stacks (counts, prefixes); on '[' push and reset; on ']' pop and set curr = prev + curr.repeat(k). Recursive alternative: parse number, skip '[', recurse for inner, skip ']', repeat. See Stack Basics, Valid Parentheses.