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.
This approach uses a stack to decode the string iteratively. Each time we encounter a '[', we push the current accumulated string and the current repetition number to the stack. When we encounter a ']', we pop from the stack, retrieve the last accumulated string and repeat the current decoded substring accordingly.
The C solution uses three stacks: one to store numbers, one to store intermediate results, and one to maintain the current result string. This allows us to handle multiple nesting levels. The solution processes the input string and iteratively constructs the decoded string based on the stack operations.
Time Complexity: O(n), where n is the length of the input string, since we scan through the string linearly while utilizing stack operations.
Space Complexity: O(n), due to the stacks used to keep track of numbers and strings.
This approach uses recursion to decode the string. The function processes the string, and upon encountering a '[', it recursively decodes the repeating substring. This allows elegant handling of nested encoded strings by delegating responsibility to sub-problems.
This C solution employs recursion by making a helper function to progressively decode the input string as it encounters opening brackets for nesting. As we move through the string, closing brackets trigger an upward return in recursion reflecting accumulation and repetition of sub-patterns.
Time Complexity: O(n), with n as length of string, since recursive steps are based on string length.
Space Complexity: O(n), mainly for recursive call stack and intermediate storage.
Python
Java
TypeScript
| Approach | Complexity |
|---|---|
| Stack-Based Iterative Decoding | Time Complexity: O(n), where n is the length of the input string, since we scan through the string linearly while utilizing stack operations. |
| Recursive Decoding Approach | Time Complexity: O(n), with n as length of string, since recursive steps are based on string length. |
| Default Approach | — |
| 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. |
Decode String - Leetcode 394 - Python • NeetCode • 136,844 views views
Watch 9 more video solutions →Practice Decode String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor