Decode String

How It Works

Strings like "3[a2[bc]]" nest repetition inside repetition, so an inner group must be fully expanded before its enclosing group — a LIFO dependency. Maintain a current string and a current count. On a digit, accumulate the number (it may be multi-digit). On '[', push both the string built so far and the count onto a stack, then reset them. On ']', pop: the new current string becomes popped-string plus current-string repeated popped-count times. Regular letters simply append.

Each character is processed once and each expansion writes each output character once, so the time is O(n + output length). Recursion gives an equivalent solution where the call stack replaces the explicit one.

Step-by-Step Visualization

Code

static String decodeString(String s) {
  Stack<Object[]> stack = new Stack<>();
  StringBuilder curr = new StringBuilder();
  int num = 0;

  for (char ch : s.toCharArray()) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch - '0');
    } else if (ch == '[') {
      stack.push(new Object[]{curr.toString(), num});
      curr = new StringBuilder(); num = 0;
    } else if (ch == ']') {
      Object[] top = stack.pop();
      String prev = (String) top[0];
      int count = (int) top[1];
      StringBuilder repeated = new StringBuilder(prev);
      for (int i = 0; i < count; i++) repeated.append(curr);
      curr = repeated;
    } else {
      curr.append(ch);
    }
  }
  return curr.toString();
}

// Example: decodeString("3[a2[c]]") → "accaccacc"

Tips & Gotchas

Practice Problems

• 1Decode String
• 2Number of Atoms
• 3Basic Calculator III
• 4Brace Expansion

About the Parentheses / Matching Pattern

Stacks naturally handle nested structures. Push opening symbols, pop when you find their closing match. If the stack is empty at the end and every match was correct, the expression is valid.

Common Stack Interview Problems

• Valid Parentheses
• Next Greater Element
• Largest Rectangle in Histogram
• Trapping Rain Water
• Daily Temperatures
• Decode String

Frequently Asked Questions

Other Parentheses / Matching Techniques