Decode String

MEDIUM✓ CHIP-TIMEDLC #394 — FULL STATEMENT ↗

The drill: Expand a compressed string where k[chunk] means 'repeat chunk k times', and brackets can nest arbitrarily deep — a run-length code that decodes into the full text.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An encoded string arrives using the pattern k[chunk], meaning the chunk inside those brackets repeats k times in the decoded output.

These bracketed groups can nest inside one another to any depth, and a decoded chunk can itself contain more k[...] patterns that need expanding before the outer repeat count applies.

Everything outside the bracket patterns is ordinary text and passes through unchanged. The drill hands back the single fully expanded string once every nested pattern has been unpacked.

EX 01

s = "2[xy]"

→ "xyxy"

SINGLE FLAT BRACKET

EX 02

s = "3[p]4[qr]"

→ "pppqrqrqrqr"

TWO SIBLING GROUPS BACK TO BACK

EX 03

s = "2[3[e]]"

→ "eeeeee"

NESTED COUNTS MULTIPLY, 2*3

encoded string stays short but nesting can run several levels deep
repeat counts k are positive integers, always at least 1
brackets always come in matched, well-formed pairs
plain letters outside brackets pass through untouched

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A nested k[...] can't be expanded until everything inside it is fully resolved first. What ordering principle handles 'finish the inner thing before the outer thing' for free?

HINT 2 THE STRUCTURE

Two pieces of state pile up as you go deeper: the text built so far at this level, and the repeat count waiting to multiply whatever comes next. Something needs to hold one frame of both per '['.

HINT 3 ONE STEP FROM THE ANSWER

On '[', push the current string and the current number, then reset both to start fresh. On ']', pop that count and outer string, and set current = outer + count × current. Digits accumulate into a running number; letters just append.

COACH'S BOARD — THE PATTERN, STEP BY STEP

FRAMES INSIDE FRAMESPATTERN · STACK OF FRAMESs = "2[3[e]]"

[

]

FRAME STACK (string, count) · CURRENT

— empty —

STEP 1

Push the string-so-far and its pending multiplier on '[' ; on ']' pop them and fold count×current back in. Nesting resolves itself.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/decode-string.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []  # (string built so far, pending multiplier)
        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 == "]":
                prev, count = stack.pop()
                current = prev + current * count
            else:
                current += ch
        return current

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 18 LN

class Solution:
    def decodeString(self, s: str) -> str:
        while "[" in s:
            # the last '[' is always an innermost, unnested bracket
            i = s.rindex("[")
            j = s.index("]", i)
            k = i
            while k > 0 and s[k - 1].isdigit():
                k -= 1
            count = int(s[k:i])
            s = s[:k] + s[i + 1 : j] * count + s[j + 1 :]
        return s

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 12 LN

class Solution {
    public String decodeString(String s) {
        Deque<String> stringStack = new ArrayDeque<>();
        Deque<Integer> countStack = new ArrayDeque<>();
        StringBuilder current = new StringBuilder();
        int num = 0;
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            } else if (ch == '[') {
                stringStack.push(current.toString());
                countStack.push(num);
                current = new StringBuilder();
                num = 0;
            } else if (ch == ']') {
                int count = countStack.pop();
                String prev = stringStack.pop();
                StringBuilder folded = new StringBuilder(prev);
                for (int c = 0; c < count; c++) {
                    folded.append(current);
                }
                current = folded;
            } else {
                current.append(ch);
            }
        }
        return current.toString();
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 29 LN

class Solution {
    public String decodeString(String s) {
        while (s.contains("[")) {
            // the last '[' is always an innermost, unnested bracket
            int i = s.lastIndexOf("[");
            int j = s.indexOf("]", i);
            int k = i;
            while (k > 0 && Character.isDigit(s.charAt(k - 1))) {
                k--;
            }
            int count = Integer.parseInt(s.substring(k, i));
            String chunk = s.substring(i + 1, j);
            StringBuilder expanded = new StringBuilder();
            for (int c = 0; c < count; c++) {
                expanded.append(chunk);
            }
            s = s.substring(0, k) + expanded + s.substring(j + 1);
        }
        return s;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED