Decode String

A string has been compressed with the rule k[text], which stands for text written out k times in a row. For example 3[ab] means ababab. The pieces can be nested, as in 2[x2[y]] = xyyxyy, and can be mixed with plain letters, as in q2[r]s = qrrs.

Given a compressed string s, return the fully expanded string.

You may assume s is well formed: brackets are balanced, every [ is directly preceded by a positive integer k (which may have several digits), and digits appear only as repeat counts, never in the original text.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits and square brackets
• 1 <= k <= 300
• The decoded string has length at most 105.

Pattern Path · Stacks · problem 46 of 169

Start simple

Repeatedly find an innermost k[...] with no brackets inside, expand it, and rebuild the string until no brackets remain: O(L·d) time for output length L and nesting depth d, with lots of copying.

The key idea

Nested brackets are processed inside-out, and the innermost open group is always the most recent one, which is exactly what a stack tracks.

Scan the string once while keeping two things: current, the decoded text of the group you are inside, and num, the repeat count being read. Then:

• a digit: num = num * 10 + digit (counts can have several digits);
• [: push (current, num), then reset both, since a new group starts;
• ]: pop (previous, k) and set current = previous + current * k, which closes the group and glues it onto the text that came before it;
• a letter: append it to current.

When the scan ends, current is the answer. Each saved prefix waits on the stack until its group closes, so nesting of any depth is handled. A recursive descent parser (a function that decodes until it meets a ]) is an equivalent alternative.

Complexity

• Time: O(L) for output length L
• Space: O(L)

Python

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []      # (text before the group, repeat count) for each open "["
        current = ""
        num = 0
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == "[":
                stack.append((current, num))
                current, num = "", 0
            elif ch == "]":
                previous, k = stack.pop()
                current = previous + current * k
            else:
                current += ch
        return current

JavaScript

var decodeString = function(s) {
  const stack = []; // [text before the group, repeat count] for each open "["
  let current = "";
  let num = 0;
  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + Number(ch);
    } else if (ch === "[") {
      stack.push([current, num]);
      current = "";
      num = 0;
    } else if (ch === "]") {
      const [previous, k] = stack.pop();
      current = previous + current.repeat(k);
    } else {
      current += ch;
    }
  }
  return current;
};

What the interviewer is checking

This tests parsing with a stack: handling nesting, multi-digit numbers and the "save context, then restore it" step cleanly.

Mistakes to avoid

• Reading only one digit, so 12[a] becomes "aa" preceded by garbage.
• Forgetting to reset the count after pushing it on [.
• Dropping the letters that appear before a bracket group or after the last ].

Follow-ups to expect

• Write the encoder that produces the shortest string. (Interval DP over substrings.)
• Return only the character at index i. (Track lengths, avoid expanding.)
• Solve it recursively. (Parse until the matching bracket.)

In real software

Run-length style expansion appears in template engines, in repeat syntax for sequence and pattern languages, and in any parser that must handle nested groups such as JSON or arithmetic expressions.

Practice next