Decode String LeetCode Solution (Medium) (2026)

Approach Summary

Use stack to track (current_string, repeat_count). On ], pop and repeat the current segment.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

Nested repetition like 3[a2[c]] requires tracking two pieces of state as you scan: the string built so far at the current nesting level and the repeat count that governs it. Use a stack of (previous_string, repeat_count) pairs. On a digit, accumulate the full number (digits can be multi-character). On an opening bracket, push the current string and number onto the stack and reset both. On a closing bracket, pop the pair, repeat the current string count times, and append it to the popped previous string — this reconstructs the inner level and splices it into the outer one. Ordinary letters are appended to the current string. Each character is processed once, and each push/pop is O(1), though the output itself can be exponential in the nesting depth, which bounds the total work.

Each character is scanned once and each stack operation is O(1) — but the decoded output can be exponential, so the worst case is O(final output length). The stack holds one pair per nesting level — O(depth).

Solution Code

Solution

public String decodeString(String s) {
    Deque<String> strStack = new ArrayDeque<>();
    Deque<Integer> numStack = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int num = 0;
    for (char ch : s.toCharArray()) {
        if (Character.isDigit(ch)) {
            num = num * 10 + (ch - '0');
        } else if (ch == '[') {
            strStack.push(cur.toString());
            numStack.push(num);
            cur = new StringBuilder();
            num = 0;
        } else if (ch == ']') {
            StringBuilder prev = new StringBuilder(strStack.pop());
            int k = numStack.pop();
            prev.append(cur.toString().repeat(k));
            cur = prev;
        } else {
            cur.append(ch);
        }
    }
    return cur.toString();
}

string decodeString(const string& s) {
    vector<string> strStack;
    vector<int> numStack;
    string cur;
    int num = 0;
    for (char ch : s) {
        if (isdigit(ch)) {
            num = num * 10 + (ch - '0');
        } else if (ch == '[') {
            strStack.push_back(cur);
            numStack.push_back(num);
            cur = "";
            num = 0;
        } else if (ch == ']') {
            string prev = strStack.back(); strStack.pop_back();
            int k = numStack.back(); numStack.pop_back();
            string segment = cur;
            for (int i = 1; i < k; i++) cur += segment;
            cur = prev + cur;
        } else {
            cur += ch;
        }
    }
    return cur;
}

def decode_string(s: str) -> str:
    stack = []
    cur = ''
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == '[':
            stack.append((cur, num))
            cur, num = '', 0
        elif ch == ']':
            prev, k = stack.pop()
            cur = prev + cur * k
        else:
            cur += ch
    return cur

function decodeString(s) {
  const stack = [];
  let cur = '';
  let num = 0;
  for (const ch of s) {
    if (/d/.test(ch)) num = num * 10 + Number(ch);
    else if (ch === '[') {
      stack.push([cur, num]);
      cur = ''; num = 0;
    } else if (ch === ']') {
      const [prev, k] = stack.pop();
      cur = prev + cur.repeat(k);
    } else cur += ch;
  }
  return cur;
}

Edge Cases to Watch

Multi-digit repeat counts like 10[a]
Deeply nested patterns like 3[a2[b1[c]]]
Letters before any bracket — appended normally
Empty encoded string

Algorithmic Pattern

Master the Stack Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Stack pattern.

Framework: Stack • Interview Prep: Tested at FAANG • Explore all Stack problems & invariants →

How to Recognize This Pattern

Nested repeated patterns
k[encoded_string]

Complexity Analysis

Time Complexity

O(n · k)

Space Complexity

O(n)

Frequently Asked Questions

What is the optimal time and space complexity for Decode String?

The optimal solution for Decode String achieves O(n · k) runtime complexity and requires O(n) auxiliary space. Each character is scanned once and each stack operation is O(1) — but the decoded output can be exponential, so the worst case is O(final output length). The stack holds one pair per nesting level — O(depth).

How do I identify that Decode String requires the Stack pattern?

In technical interviews, look for key problem signals: Nested repeated patterns; k[encoded_string]. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Stack strategy.

What critical edge cases must be handled in Decode String?

Essential edge cases to verify include: Multi-digit repeat counts like 10[a]; Deeply nested patterns like 3[a2[b1[c]]]; Letters before any bracket — appended normally; Empty encoded string. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Decode String?

Decode String is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Google, Amazon, Bloomberg.

Decode String LeetCode Solution