DSA problem
Decode String
Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. You may assume the input is always valid; for example, there are no extra white spaces, the square brackets are well-formed, and the digits are only used for the repeat numbers.
The grammar is small but recursive: a decoded string is a sequence of literal characters and k[…] blocks, and the body of every k[…] block is itself a decoded string. That recursive structure is exactly what makes a recursive (or stack-based) parser the natural fit. Naive string repetition still gives the correct answer, but writing it cleanly requires either explicit stacks or recursion.
The optimal recursive approach scans the input with a shared cursor. While the character is a digit, accumulate it into the current repeat count k. When you hit [, advance past it and recurse to decode the inner string; the recursion stops when it sees ]. After the recursion returns, append the inner result k times to the current buffer. Any plain letter is appended directly.
Because the recursion only descends when a [ is encountered and unwinds on the matching ], bracket pairing is handled implicitly by the call stack. Each character of the output is produced exactly once, giving O(N * maxK) time, where N is the input length and maxK is the largest repeat count. The auxiliary space is O(d) recursion depth plus O(N * maxK) for the output buffer.
Examples
s = "3[a]2[bc]""aaabcbc"s = "3[a2[c]]""accaccacc"s = "2[abc]3[cd]ef""abcabccdcdcdef"Constraints
- 1 <= s.length <= 30
- s consists of lowercase English letters, digits, and square brackets '[]'.
- s is guaranteed to be a valid input.
- All the integers in s are in the range [1, 300].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.