A deploy-runbook interpolator expanded templates like 3[retry] and nested 2[backoff3[retry]] into the command list. The intern scanned from each [ to the matching ], decoded the inside, and repeated. Staging’s 3[retry] expanded clean. A nested 3[a2[c]] still returned; a deeper template spent its budget on matching-bracket scans a pair of stacks already held as the unfinished outer fragment.

Decode String asks you to expand nested k[encoded] into the repeated letters. Finding each matching ] and recursing uses that and still pays extra scans. The unfinished outer fragment is already the top of a stack.

This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about pending counts and unfinished fragments so a ] is an expand, not a rescan. Matching brackets is Valid Parentheses — checker, not expander.

The problem

Given a string s of lowercase letters, digits, and square brackets, return the decoded string. The pattern k[encoded] means the inner string repeated k times; brackets nest, and k may be more than one digit. Letters outside any bracket copy through as-is, digits appear only as k, and the encoding is well-formed.

s = "3[a]2[bc]"      →  "aaabcbc"
s = "3[a2[c]]"       →  "accaccacc"
s = "2[abc]3[cd]ef"  →  "abcabccdcdcdef"
s = "12[a]"          →  "aaaaaaaaaaaa"

Note: Matching brackets without expanding is Valid Parentheses. Emitting every well-formed wrapping is Generate Parentheses. This prompt expands one already-valid encoding.

Find the matching bracket, then recurse, is the honest brute force

When you hit a digit, parse k, scan from the following [ to the matching ] — the same nest-depth walk Valid Parentheses uses on one bracket type — recurse on the inside, and concatenate k copies. Correct. Each match is an extra scan.

String decodeStringScan(String s) {
    return decodeRange(s, 0, s.length());
}

String decodeRange(String s, int lo, int hi) {
    StringBuilder out = new StringBuilder();
    int i = lo;
    while (i < hi) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') {
            int k = 0;
            while (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                k = k * 10 + (s.charAt(i) - '0');
                i++;
            }
            int depth = 0;
            int j = i;
            while (j < hi) {
                if (s.charAt(j) == '[') {
                    depth++;
                } else if (s.charAt(j) == ']') {
                    depth--;
                    if (depth == 0) {
                        break;
                    }
                }
                j++;
            }
            String inner = decodeRange(s, i + 1, j);
            for (int r = 0; r < k; r++) {
                out.append(inner);
            }
            i = j + 1;
        } else {
            out.append(c);
            i++;
        }
    }
    return out.toString();
}

At n = 20 the matching-bracket walk is a rounding error. Nested k[k[k[…]]] pays that scan at every close for a question whose unfinished outer fragment is already the top of a stack.

Push the count, expand on the close

Walk left to right. Keep a current StringBuilder and two ArrayDeques: pending counts and pending fragments. A single stack of (count, fragment) frames is the same idea.

  • Digit: accumulate k = k * 10 + digit.
  • [: push k and the current fragment, then reset both (k = 0, new empty current).
  • Letter: append to current.
  • ]: pop count and previous fragment; append current repeated that many times onto previous; that becomes the new current.

Digits accumulate; 12[a] is twelve copies, not one then two. Walk 3[a2[c]] — nested ] expands the inner first, then the outer multiplies that result.

s = "3[a2[c]]"

3     k=3
[     push 3, cur=""      counts: 3      frags: ""       cur="", k=0
a     cur="a"
2     k=2
[     push 2, cur="a"     counts: 3 2    frags: "" "a"   cur="", k=0
c     cur="c"
]     pop 2, prev="a"     "a" + "c"×2 = "acc"            cur="acc"
]     pop 3, prev=""      "" + "acc"×3 = "accaccacc"     cur="accaccacc"
end   →  "accaccacc"

The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack.

String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> frags = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            counts.push(k);
            frags.push(cur);
            cur = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            int times = counts.pop();
            StringBuilder prev = frags.pop();
            for (int r = 0; r < times; r++) {
                prev.append(cur);
            }
            cur = prev;
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

The parse is one pass over s, but repeating inner strings means time is proportional to decoded length, not encoded length. Nested 2[2[2[a]]] grows exponentially in depth. Space tracks decoded length plus the two deques. Saying O(n) for n = s.length() hides the bill; say output length out loud.

Note: Empty inner 3[] is usually outside the spec — at the board, ask. Letters with no brackets ("abc") never hit [ or ]; current is the answer and the deques stay empty.

What interviewers usually poke next

  • Multi-digit k. Say k = k * 10 + digit out loud. Treating 12 as two counts yields aa, not twelve as.
  • Nested close order. Inner ] expands first; the outer multiplies that result. The matching-bracket recurse does the same; the deques just do not rescan.
  • Letters outside brackets. ef in 2[abc]3[cd]ef appends to current with no count. They are not an error.
  • Output size. Encoded length 30 can still explode. Time and space track decoded length, not s.length().
  • Only matching. That is Valid Parentheses. A checker does not expand 3[a].
  • Generate every wrapping. That is Generate Parentheses, not a decoder.

You are done with this problem when you can accumulate multi-digit k, expand on ] rather than rescan, and say why time follows the output length.