Decode String in a Coding Interview: Two Stacks vs Recursion

"Decode String" (3[a2[c]] becomes accaccacc) looks like a parsing puzzle, but it is really a test of whether you can manage nested state cleanly. There are two solid approaches, and knowing both lets you pick the one you can explain best under pressure.

The rules

• k[encoded] means repeat encoded exactly k times.
• k can have more than one digit (12[ab]).
• Brackets can nest to any depth.
• Plain letters outside brackets are copied as they are.

Say these out loud before coding. The multi-digit number is the detail most candidates miss.

Approach 1: two stacks

Keep the string you are building and the current number. When you see [, push both onto stacks and start fresh. When you see ], pop and combine.

def decode_string(s):
    counts, prefixes = [], []
    cur, num = [], 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == '[':
            counts.append(num)
            prefixes.append(cur)
            cur, num = [], 0
        elif ch == ']':
            k = counts.pop()
            cur = prefixes.pop() + cur * k
        else:
            cur.append(ch)
    return ''.join(cur)

Using a list of characters instead of string concatenation keeps the inner loop cheap in Python.

Approach 2: recursion with a shared index

Each call decodes until it hits a ] and returns what it built. The bracket structure maps directly onto the call stack, which some interviewers find easier to follow.

def decode_string(s):
    i = 0
    def helper():
        nonlocal i
        out, num = [], 0
        while i < len(s):
            ch = s[i]
            i += 1
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == '[':
                inner = helper()
                out.append(inner * num)
                num = 0
            elif ch == ']':
                return ''.join(out)
            else:
                out.append(ch)
        return ''.join(out)
    return helper()

Complexity

Both run in time proportional to the length of the output, since every output character is written at least once. Space is the output plus the nesting depth. If the interviewer asks about adversarial input like 100[100[100[a]]], point out the output is a million characters and no algorithm can beat writing it.

Test cases worth saying out loud

• 3[a]2[bc] gives aaabcbc (siblings)
• 3[a2[c]] gives accaccacc (nesting)
• 2[abc]3[cd]ef gives abcabccdcdcdef (trailing letters)
• 10[a] (multi-digit count)
• abc (no brackets at all)

Follow-ups

• Validate the input first? Use a counter for brackets and reject a digit not followed by [.
• Stream the output? The recursive version can yield chunks instead of building a whole string.
• Encode instead of decode? That becomes an interval DP problem and is much harder; say so honestly.

If you practice these patterns and want help while you work through timed online assessments, the Linkjob AI interview copilot gives real-time hints during coding rounds.

Disclosure: I'm part of the team at Linkjob AI. These notes are general interview prep.