Decode string: expand nested k[text] repeats

A string is encoded with the rule k[text]: the text inside the brackets is repeated k times. k is a positive integer that may have several digits, encoded parts can be nested, and plain letters can sit between and around them. Return the fully decoded string.

Interface

Unless you agree on a different interface with the interviewer, assume:

• decode(s: str) -> str — the expanded string.

Example

decode("a2[b]c")      ->  "abbc"
decode("z10[q]")      ->  "zqqqqqqqqqq"        # a two-digit count
decode("2[x3[yz]]w")  ->  "xyzyzyzxyzyzyzw"    # 3[yz] = "yzyzyz", so x3[yz] = "xyzyzyz", twice, then "w"
decode("3[a2[c]]")    ->  "accaccacc"

Constraints

• s is valid: brackets balance, every [ follows its count, every count is followed by [, no brackets are empty.
• Only lowercase letters, digits, [ and ]. Digits appear only in counts, which have no leading zeros.
• 1 <= k <= 300; the decoded string is at most 100,000 characters.

Clarifying questions

• Can I assume the input is always valid?
• Can a count be more than one digit? Can it be 0?
• Can the decoded text contain digits?
• How long can the output get? Should I worry about memory?

What a strong answer covers

• A stack of (text so far, count) pairs: on [ push and start fresh, on ] pop and append the current text repeated count times; digits accumulate into a multi-digit count.
• Or recursion with a shared index that returns at each ].
• Building strings with lists and join, not repeated concatenation in a loop.
• Time and space proportional to the output length.
• Edge cases: no brackets at all, 1[a], deep nesting, letters right after a ].

Follow-ups

• Write the encoder: produce the shortest encoding of a string.
• The decoded output would be gigabytes. Return the character at position i without building it.
• Validate the input and report the first error instead of assuming it is valid.