Decode String
01 · Problem
You are given an encoded string s. The encoding rule is k[text], meaning the bracketed text should be written out exactly k times in a row, where k is a positive integer. Encodings may be nested, e.g. 2[a3[b]].
Return the fully decoded string.
You may assume the input is always well-formed: brackets are balanced, there are no stray spaces, every number is immediately followed by [, and digits only ever appear as repeat counts (the plain text never contains digits).
02 · Examples
s = "2[x]3[yz]"
"xxyzyzyz"
"x" written twice followed by "yz" written three times gives "xx" + "yzyzyz".
s = "2[m3[n]]"
"mnnnmnnn"
The inner part "m3[n]" decodes to "mnnn", and writing it twice gives "mnnnmnnn".
s = "3[ab]2[c]de"
"abababccde"
"ababab" + "cc" + the literal tail "de".
03 · Constraints
- 011 <= s.length <= 30
- 02s consists of lowercase English letters, digits, and square brackets '[]'
- 03s is a valid encoding and every integer k is in the range [1, 300]
- 04The decoded string has length at most 105
04 · Optimal complexity
- Time
- O(n + L)
- Space
- O(n + L)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.