#394 Decode String

frequently reported atBloomberg ByteDance / TikTok Google Meta Amazon Microsoft

the problem

In plain words

Decode a string encoded as k[encoded], meaning the inside is repeated k times. Encodings can nest, e.g. "3[a2[c]]". Digits only appear as repeat counts.

in s = "3[a]2[bc]"

out "aaabcbc"

in s = "3[a2[c]]"

out "accaccacc"

in s = "2[abc]3[cd]ef"

out "abcabccdcdcdef"

1 ≤ s.length ≤ 30
1 ≤ k ≤ 300
s is a valid encoding; the output length ≤ 10⁵

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack for matching & nesting String parsing

On '[' you start a new inner string, but you must remember the outer text and the count. On ']' you finish the inner string, repeat it, and glue it back onto the outer text — save on open, restore on close: a stack.

solutions

From brute force to optimal

The first ']' closes an innermost group. Expand it in the string and start over.

Find the first ']' and the last '[' before it.
Read the number before '['.
Replace k[inner] with inner repeated k times.
Repeat until no '[' remains.

timeO(b · L)

b bracket groups, and each rewrite copies the whole string, up to the output length L.

spaceO(L)

The rewritten string.

javajava.util.*

1class Solution {2    public String decodeString(String s) {3        while (s.indexOf('[') >= 0) {4            int close = s.indexOf(']');            // first ']' closes the innermost group5            int open = s.lastIndexOf('[', close);  // its matching '['6            int start = open;7            while (start > 0 && Character.isDigit(s.charAt(start - 1))) start--;8            int k = Integer.parseInt(s.substring(start, open));9            String inner = s.substring(open + 1, close);10            s = s.substring(0, start) + inner.repeat(k) + s.substring(close + 1);11        }12        return s;13    }14}

cur builds the current level. '[' pushes (k, cur) and starts fresh; ']' pops them and appends the repeated inner text.

Digit → k = k·10 + digit (counts can be multi-digit).
'[' → push k and cur; cur = new builder; k = 0.
']' → cur = outer.pop() + cur repeated counts.pop() times.
Letter → append to cur.

timeO(L · d)

Each output character is copied once per enclosing bracket level (d = max nesting depth).

spaceO(L)

The builders on the stack plus the result.

javajava.util.*

1class Solution {2    public String decodeString(String s) {3        Deque<Integer> counts = new ArrayDeque<>();4        Deque<StringBuilder> outer = new ArrayDeque<>(); // text built before each '['5        StringBuilder cur = new StringBuilder();6        int k = 0;7        for (char c : s.toCharArray()) {8            if (Character.isDigit(c)) {9                k = k * 10 + (c - '0');        // numbers can have several digits ("12[a]")10            } else if (c == '[') {11                counts.push(k);                // save the context, start fresh inside12                outer.push(cur);13                cur = new StringBuilder();14                k = 0;15            } else if (c == ']') {16                String inner = cur.toString();17                cur = outer.pop().append(inner.repeat(counts.pop())); // glue back onto the outside18            } else {19                cur.append(c);20            }21        }22        return cur.toString();23    }24}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public String decodeString(String s) {3        Deque<Integer> counts = new ArrayDeque<>();4        Deque<StringBuilder> outer = new ArrayDeque<>(); // text built before each '['5        StringBuilder cur = new StringBuilder();6        int k = 0;7        for (char c : s.toCharArray()) {8            if (Character.isDigit(c)) {9                k = k * 10 + (c - '0');        // numbers can have several digits ("12[a]")10            } else if (c == '[') {11                counts.push(k);                // save the context, start fresh inside12                outer.push(cur);13                cur = new StringBuilder();14                k = 0;15            } else if (c == ']') {16                String inner = cur.toString();17                cur = outer.pop().append(inner.repeat(counts.pop())); // glue back onto the outside18            } else {19                cur.append(c);20            }21        }22        return cur.toString();23    }24}

decode() reads until ']' and returns its text; '[' calls decode() for the inner part.

Shared index i.
Digit → build k. '[' → append decode() repeated k times. ']' → return. Letter → append.

timeO(L · d)

Same copying as the two-stack version.

spaceO(L)

Builders along the recursion path (depth d) plus the result.

javajava.util.*

1class Solution {2    private int i; // shared read position3 4    public String decodeString(String s) {5        i = 0;6        return decode(s);7    }8 9    private String decode(String s) {10        StringBuilder sb = new StringBuilder();11        int k = 0;12        while (i < s.length()) {13            char c = s.charAt(i++);14            if (Character.isDigit(c)) k = k * 10 + (c - '0');15            else if (c == '[') { sb.append(decode(s).repeat(k)); k = 0; } // the call stack is the stack16            else if (c == ']') return sb.toString();17            else sb.append(c);18        }19        return sb.toString();20    }21}

in the room

How to say it in the interview

talk track

Ask: can counts have several digits? (Yes — "10[a]".) Can letters appear outside brackets? (Yes.)
Say: "each '[' saves my current context, each ']' restores it — that's a stack."
Offer recursion as the same idea with the call stack.

traps

Reading only one digit for k — "12[a]" becomes "2[a]" after a stray '1'.
Forgetting to reset k to 0 after pushing it.

what they ask next

Follow-ups

Number of Atoms (LC 726)?

Same stack-of-contexts idea with a map of counts per level; multiply the inner map on ')'.

before you submit

Edge cases to test

Counts with several digits: "10[x]" (k can be up to 300).
Letters outside any brackets: "2[abc]3[cd]ef" ends with "ef".
A tiny input with a huge output: "300[300[a]]" decodes to 90,000 characters.

practise next