Skip to main content

20. Decode String

mediumAsked at Wix

Expand a run-length encoded string like '3[a2[bc]]' into 'abcbcabcbcabcbc' — Wix applies this exact nested-expansion pattern to CSS shorthand parsing and to template-variable substitution in their email and site-builder engines.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an encoded string, return its decoded form. The encoding rule is k[encoded_string], where encoded_string inside brackets is repeated exactly k times. The input is always valid: no extra white spaces, brackets are well-formed, digits represent repetition counts only, and the original data does not contain digits.

Constraints

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'
  • All the integers in s are in the range [1, 300]

Examples

Example 1

Input
s = "3[a]2[bc]"
Output
"aaabcbc"

Example 2

Input
s = "3[a2[c]]"
Output
"accaccacc"

Explanation: Inner 2[c] expands to 'cc', then outer 3[a + cc] = 'accaccacc'

Approaches

1. Recursive descent

Use an index pointer and recurse when a '[' is encountered; unwind back to the caller when ']' is hit. Naturally models nested structure.

Time
O(max_expansion)
Space
O(depth * max_expansion)
function decodeString(s) {
  let i = 0;

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

  return decode();
}

Tradeoff:

2. Iterative stack

Use two stacks — one for counts and one for partial strings. On '[', push current state. On ']', pop and multiply.

Time
O(max_expansion)
Space
O(depth)
function decodeString(s) {
  const countStack = [];
  const strStack = [];
  let current = '';
  let num = 0;

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + Number(ch);
    } else if (ch === '[') {
      countStack.push(num);
      strStack.push(current);
      current = '';
      num = 0;
    } else if (ch === ']') {
      const count = countStack.pop();
      const prev = strStack.pop();
      current = prev + current.repeat(count);
    } else {
      current += ch;
    }
  }

  return current;
}

Tradeoff:

Wix-specific tips

Wix interviewers use this to see whether you naturally reach for a stack when nesting depth is variable. Naming the pattern 'bracket-matched stack' and noting that it underpins CSS-in-JS template parsing at Wix lands you in territory that's directly relevant to the team's daily work.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Decode String and other Wix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →