#394 - Decode String

MediumStack

Given an encoded string of the form k[encoded_string], return its decoded string. The rule is: the encoded_string inside the square brackets is repeated exactly k times. Nesting is allowed (e.g. 3[a2[c]] → "accaccacc"). Input is always valid: no extra spaces, brackets are well-formed, and k is a positive integer.

Input	Output
s = "3[a]2[bc]"	"aaabcbc"
s = "3[a2[c]]"	"accaccacc"
s = "2[abc]3[cd]ef"	"abcabccdcdcdef"

Solution Space

Try it

/**
 * Decodes an encoded string where k[encoded] means repeat encoded k times.
 *
 * @param s Encoded string with nested bracket patterns
 * @returns Fully decoded string
 */
export function decodeString(s: string): string {
  const countStack: number[] = [];
  const stringStack: string[] = [];
  let current = "";
  let k = 0;

  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      // Build multi-digit number
      k = k * 10 + Number(ch);
    } else if (ch === "[") {
      // Save current context and start a new scope
      countStack.push(k);
      stringStack.push(current);
      current = "";
      k = 0;
    } else if (ch === "]") {
      // Pop and repeat: prefix + current × count
      const repeatCount = countStack.pop()!;
      const prefix = stringStack.pop()!;
      current = prefix + current.repeat(repeatCount);
    } else {
      current += ch;
    }
  }

  return current;
}

Approach: two-stack – one stack for repeat counts, one for partially built strings. On `[`, push current state and reset. On `]`, pop and combine.

Time: O(n · maxK) – where n is the length of the decoded output and maxK is the maximum nesting repeat factor.

Space: O(n) – for the stacks and intermediate strings.

Alternative approaches:

Approach	Idea	Time	Space
Recursion	Treat each k[...] as a recursive call; use an index pointer to track position	O(n · maxK)	O(n) (call stack)
Single stack	Push everything onto one stack; on ], pop until [ to build the substring, then pop the count	O(n · maxK)	O(n)

Why the two-stack method is preferred: It avoids recursion overhead and is more explicit about state management than the single-stack variant, making the logic easier to follow.

#155 Min Stack

#735 Asteroid Collision