Decode String - Solution & Explanation
Problem Statement
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 <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.- All the integers in
sare in the range[1, 300].
Approach Overview
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 1: Stack-Based Iterative Decoding
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.
Complexity
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.
Approach 2: Recursive Decoding Approach
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.
Complexity
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.
Approach 3: Default Approach
Code
Python
Java
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Decode String - Leetcode 394 - Python • NeetCode • 144,345 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Decode String easy or hard?
Decode String Python/Java solution
How to solve Decode String in O(n)?
What is the best approach for Decode String?
Is Decode String asked at Google/Amazon/Meta?
What data structure is used in Decode String?
What is the time complexity of Decode String?
Ready to solve this problem?
Practice Decode String with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor