Decode String
Last Updated: April 3, 2026
Understanding the Problem
We have a string where patterns like k[...] mean "repeat whatever is inside the brackets k times." The twist is that these patterns can be nested. 3[a2[c]] means: first decode the inner 2[c] to get "cc", combine it with the "a" before it to get "acc", and then repeat that whole thing 3 times to get "accaccacc".
So we are dealing with nested structures, similar to how parentheses nest in mathematical expressions. When we see an opening bracket, we need to "remember" what we were building so far and what multiplier to use, go decode the inside, and then come back and apply the multiplier. This nesting behavior is a strong signal that either a stack or recursion will be the right tool.
The key observation is that the innermost brackets should be resolved first, and their result feeds into the outer brackets. This inside-out processing is exactly what a stack gives us naturally.
Key Constraints:
1 <= s.length <= 30→ The input string is extremely short. Even an O(2^n) approach would work on the input. But the output can be up to 10^5 characters long, so the real cost is in building the decoded string.- Integers are in range
[1, 300]→ Repeat counts can be multi-digit (up to 3 digits). We need to parse numbers like300, not just single digits. sis guaranteed to be valid → No need to handle malformed inputs. Every[has a matching], and every[is preceded by a number.
Approach 1: Brute Force (Repeated String Replacement)
Intuition
The most straightforward idea: find the innermost bracket pair (one that contains no other brackets inside it), decode it by repeating the string, replace it in the original string, and repeat until no brackets remain.
This works because the innermost brackets are always safe to decode first. They don't contain any nested structures, so we can just repeat their content and substitute it back. After each substitution, what was previously nested becomes one level less deep.
Think of it like peeling an onion from the inside out. Each pass resolves one layer of nesting.
Algorithm
- Scan the string for the innermost bracket pair: find a
]and then look backwards for its matching[. - Extract the number before the
[and the string between[and]. - Replace the entire
number[string]with the repeated string. - Repeat until no brackets remain in the string.
Example Walkthrough
Code
- Time Complexity: O(d n maxK). Each pass resolves one nesting layer. Finding brackets and building substrings takes O(n) per pass, and the string grows by a factor of maxK at each level.
- Space Complexity: O(output length). Intermediate strings are built during each replacement. The final output can be up to 10^5 characters.
This approach works but rebuilds the entire string on every pass. What if we could process the string in a single left-to-right scan, building the result as we go?
Approach 2: Stack-Based (Optimal)
Intuition
Instead of repeatedly scanning and replacing, we can process the string in one left-to-right pass using a stack. As we walk through the string, we build the current decoded string character by character. When we hit a [, we "save" what we have so far (the current string and the repeat count) by pushing them onto the stack, and start fresh for the inner content. When we hit a ], we pop the saved state, repeat the current string the required number of times, and append it to the saved string.
The stack acts as a memory bank. Every time we enter a new bracket level, we deposit our current progress (the string built so far and the repeat count) into the stack. While inside the brackets, we work on a fresh string. When we exit the brackets, we withdraw our saved progress and combine it with the freshly decoded inner content.
This naturally handles nesting of any depth. For 3[a2[c]], when we hit the inner [, we push what we had ("a" and count 2). We decode "c" inside. When we hit the inner ], we pop and get "a" + "c"2 = "acc". When we hit the outer ], we pop the original empty string and count 3, giving us "acc"3 = "accaccacc".
Algorithm
- Initialize an empty stack,
currentStringas empty, andcurrentNumas 0. - Iterate through each character in the string:
- If it's a digit, build the number:
currentNum = currentNum * 10 + digit(handles multi-digit numbers like 12 or 300). - If it's
[, push(currentString, currentNum)onto the stack, then resetcurrentStringto empty andcurrentNumto 0. - If it's
], pop(previousString, repeatCount)from the stack. SetcurrentString = previousString + currentString repeated repeatCount times. - If it's a letter, append it to
currentString. - Return
currentString.
Example Walkthrough
Code
- Time Complexity: O(n + output length). We iterate through the input string once, doing O(1) work per character. The string repetition and concatenation produce the output, so total work is proportional to the decoded output length.
- Space Complexity: O(n + output length). The stack depth is proportional to the nesting depth (at most O(n)). Intermediate strings on the stack plus the final output take space proportional to the output length.
The stack approach is already optimal in terms of time. But there is an alternative way to think about this: recursion. Instead of manually managing a stack, we can let the call stack do the work.
Approach 3: Recursive
Intuition
The structure of this problem is inherently recursive. A valid encoded string is either a sequence of regular characters (base case) or a number followed by [encoded_string] where encoded_string is itself a valid encoded string (recursive case).
So we can write a function that processes characters one by one. When it sees a digit, it reads the full number, expects a [, recursively decodes the content until the matching ], and repeats the result. When it sees a letter, it just appends it. The key trick is using a shared index variable so that when a recursive call returns, the caller knows where it left off in the string.
Algorithm
- Maintain a pointer
indexthat tracks our position in the string. - Define a recursive function
decode(): - Initialize a result string.
- While
indexis within bounds and the current character is not]: - If it's a digit, parse the full number, skip the
[, recursively decode until], skip the], and append the repeated decoded string to result. - If it's a letter, append it to result and advance
index. - Return the result string.
- Call
decode()starting at index 0.
Example Walkthrough
Code
- Time Complexity: O(n + output length). Each character in the input is processed once. The string repetition produces output proportional to the decoded length.
- Space Complexity: O(n + output length). The recursion depth equals the maximum nesting depth (at most O(n)). Intermediate strings at each level contribute to the output length.