Watch 10 video solutions for Decode String, a medium level problem involving String, Stack, Recursion. This walkthrough by NeetCode has 333,550 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Example 1:
Input: s = "3[a]2[bc]" Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]" Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef"
Constraints:
1 <= s.length <= 30s consists of lowercase English letters, digits, and square brackets '[]'.s is guaranteed to be a valid input.s are in the range [1, 300].Problem Overview: You receive an encoded string where patterns like k[encoded_string] mean the substring inside the brackets repeats k times. Nested encodings are allowed, so patterns like 3[a2[c]] must be decoded from the innermost bracket outward. The goal is to return the fully expanded string.
Approach 1: Stack-Based Iterative Decoding (O(n) time, O(n) space)
This approach scans the string from left to right while using a stack to remember previous states. When you encounter a number, build the full repeat count. When you see an opening bracket [, push the current string and repeat count onto the stack and reset them for the new nested segment. When a closing bracket ] appears, pop the previous string and count, then append the current decoded segment repeated k times. Each character is processed once, so the algorithm runs in O(n) time with O(n) auxiliary space for the stack and intermediate strings. This approach works well when you want explicit control over nested structures without recursion.
Approach 2: Recursive Decoding Approach (O(n) time, O(n) space)
The recursive solution mirrors the nested structure of the encoding. When the parser encounters a number followed by [, it recursively decodes the substring inside the brackets until the matching ]. The returned decoded substring is then repeated k times and appended to the current result. Because each character in the string is processed once and recursion simply follows the bracket hierarchy, the total time complexity remains O(n). The recursion depth depends on nesting levels, giving O(n) space in the worst case due to the call stack. This method often feels more natural when working with nested grammars or recursion-based parsing.
Recommended for interviews: The stack-based approach is the one most interviewers expect. It clearly demonstrates how you manage nested structures using an explicit stack and avoids recursion depth issues. The recursive version is equally efficient and elegant, but candidates who implement the stack solution show stronger control over iterative parsing and state management.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Iterative Decoding | O(n) | O(n) | Best general solution for interviews. Handles nested patterns using an explicit stack. |
| Recursive Decoding | O(n) | O(n) | Useful when treating the encoding like a recursive grammar or when recursion feels more intuitive. |