Decode String
Description
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. The value k is guaranteed to be a positive integer.
The encoding can be nested. For example, 3[a2[c]] means the inner part 2[c] decodes to 'cc', making the content inside the outer brackets 'acc', which is then repeated 3 times to produce 'accaccacc'.
You may assume:
- The input string is always valid — brackets are well-formed and properly nested.
- The original data contains only lowercase English letters.
- Digits only appear as repeat counts before brackets (no inputs like '3a' or '2[4]').
- The integer k can be multi-digit (e.g., '10[a]' means repeat 'a' ten times).
- The length of the decoded output will never exceed 10^5.
Examples
Example 1
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Explanation: The string has two encoded segments. The first segment '3[a]' repeats 'a' three times to get 'aaa'. The second segment '2[bc]' repeats 'bc' twice to get 'bcbc'. Concatenating them gives 'aaabcbc'.
Example 2
Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: This is a nested encoding. Start from the innermost brackets: '2[c]' decodes to 'cc'. The outer bracket content becomes 'a' + 'cc' = 'acc'. Then '3[acc]' repeats 'acc' three times to produce 'accaccacc'.
Example 3
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Explanation: '2[abc]' decodes to 'abcabc'. '3[cd]' decodes to 'cdcdcd'. The trailing 'ef' is plain text. Concatenating all parts gives '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].
Editorial
Brute Force - Recursive Decoding
Intuition
The most natural way to think about this problem is recursion. The encoded string has a nested structure — brackets inside brackets — which mirrors how recursive function calls work: each call handles one level of nesting, and when it finishes, it returns its result to the caller.
Imagine reading the string like peeling layers of an onion:
- You read characters one by one.
- When you hit a number followed by '[', you know a new encoded section begins. You 'dive in' to decode that section (a recursive call).
- When you hit ']', the current section ends. You return what you've decoded so far.
- Plain letters are simply collected as you go.
The key challenge is keeping track of where you are in the string across recursive calls. We use a global index (or pass it by reference) that advances as characters are consumed. This way, when a recursive call finishes, the parent call knows exactly where to resume reading.
While this approach is correct and handles any depth of nesting, it relies on the call stack to manage nesting levels. For deeply nested inputs, this could lead to stack overflow — though with the given constraint of s.length ≤ 30, this is not a practical concern.
Step-by-Step Explanation
Let's trace through with s = "3[a2[c]]":
Step 1: Start the main recursive call. index = 0, result = "".
Step 2: Read s[0] = '3'. It's a digit. Build the number: num = 3. Advance index to 1.
Step 3: Read s[1] = '['. Opening bracket found. Advance index to 2. Make a recursive call to decode the content inside these brackets.
Step 4: (Inside recursive call, level 1) index = 2, result = "".
- Read s[2] = 'a'. It's a letter. Append to result. result = "a". index = 3.
Step 5: Read s[3] = '2'. It's a digit. Build the number: num = 2. index = 4.
Step 6: Read s[4] = '['. Opening bracket found. Advance index to 5. Make another recursive call (level 2).
Step 7: (Inside recursive call, level 2) index = 5, result = "".
- Read s[5] = 'c'. It's a letter. Append to result. result = "c". index = 6.
Step 8: Read s[6] = ']'. Closing bracket found. Return result = "c" to caller. Advance index to 7.
Step 9: (Back in level 1) Received "c" from recursive call. Repeat it 2 times: "c" × 2 = "cc". Append to result. result = "a" + "cc" = "acc".
Step 10: Read s[7] = ']'. Closing bracket found. Return result = "acc" to caller. Advance index to 8.
Step 11: (Back in main call) Received "acc" from recursive call. Repeat it 3 times: "acc" × 3 = "accaccacc". Append to result. result = "accaccacc".
Step 12: index = 8, which equals string length. Recursion complete.
Result: "accaccacc"
Recursive Decoding — Call Stack Visualization — Watch how the recursion stack grows as we encounter nested brackets, and shrinks as we close brackets and return decoded results to the caller.
Algorithm
- Maintain a global index variable that tracks the current position in the string.
- Define a recursive helper function decode():
a. Initialize an empty result string.
b. While index is within bounds and the current character is not ']':- If the character is a digit, build the full number (handling multi-digit).
- If the character is '[', advance past it and recursively call decode(). Multiply the returned string by the number, append to result.
- If the character is a letter, append it to result and advance index.
c. Advance index past the closing ']'.
d. Return the result string.
- Call decode() and return its result.
Code
#include <string>
using namespace std;
class Solution {
public:
int index = 0;
string decodeString(string s) {
index = 0;
return decode(s);
}
string decode(const string& s) {
string result;
while (index < s.size() && s[index] != ']') {
if (isdigit(s[index])) {
// Build the repeat count
int num = 0;
while (index < s.size() && isdigit(s[index])) {
num = num * 10 + (s[index] - '0');
index++;
}
// Skip '['
index++;
// Recursively decode content inside brackets
string decoded = decode(s);
// Skip ']'
index++;
// Repeat and append
while (num-- > 0) {
result += decoded;
}
} else {
// Regular letter
result += s[index];
index++;
}
}
return result;
}
};class Solution:
def decodeString(self, s: str) -> str:
self.index = 0
return self._decode(s)
def _decode(self, s: str) -> str:
result = []
while self.index < len(s) and s[self.index] != ']':
if s[self.index].isdigit():
# Build the repeat count (handle multi-digit)
num = 0
while self.index < len(s) and s[self.index].isdigit():
num = num * 10 + int(s[self.index])
self.index += 1
# Skip '['
self.index += 1
# Recursively decode content inside brackets
decoded = self._decode(s)
# Skip ']'
self.index += 1
# Repeat and append
result.append(decoded * num)
else:
# Regular letter
result.append(s[self.index])
self.index += 1
return ''.join(result)class Solution {
private int index = 0;
public String decodeString(String s) {
index = 0;
return decode(s);
}
private String decode(String s) {
StringBuilder result = new StringBuilder();
while (index < s.length() && s.charAt(index) != ']') {
if (Character.isDigit(s.charAt(index))) {
// Build the repeat count
int num = 0;
while (index < s.length() && Character.isDigit(s.charAt(index))) {
num = num * 10 + (s.charAt(index) - '0');
index++;
}
// Skip '['
index++;
// Recursively decode content inside brackets
String decoded = decode(s);
// Skip ']'
index++;
// Repeat and append
for (int i = 0; i < num; i++) {
result.append(decoded);
}
} else {
// Regular letter
result.append(s.charAt(index));
index++;
}
}
return result.toString();
}
}Complexity Analysis
Time Complexity: O(n × m)
Where n is the length of the input string and m is the maximum length of the decoded output. Each character in the input is visited exactly once during the recursion. However, string repetition operations can produce strings proportional to the output size. In the worst case with deep nesting like '2[2[2[a]]]', the output length grows exponentially relative to the input.
Space Complexity: O(n + m)
The recursion stack depth is proportional to the maximum nesting depth, which is bounded by O(n). The intermediate result strings at each recursion level can occupy O(m) space in total, where m is the decoded output length. The overall space is O(n + m).
Why This Approach Is Not Efficient
The recursive approach has two key drawbacks:
-
Call stack overhead: Each level of nesting creates a new function call on the system's call stack. While the constraint s.length ≤ 30 prevents stack overflow in practice, the recursive approach uses implicit memory (the call stack) that we cannot control. Deeply nested inputs consume stack frames that each carry overhead for return addresses, local variables, and frame pointers.
-
Harder to reason about state: The global index variable shared across recursive calls makes the code harder to understand and debug. The flow of control jumps between recursion levels, making it difficult to trace which function frame is responsible for which part of the decoding.
The key insight for improvement: we are already implicitly using a stack (the call stack). By making the stack explicit, we eliminate recursion overhead, gain full control over memory usage, and produce a more straightforward iterative solution. Instead of pausing and resuming function calls, we simply push and pop from our own data structure.
Optimal Approach - Two-Stack Iterative
Intuition
The nested bracket structure of this problem naturally maps to a stack-based solution. Think of it like reading a book with footnotes:
- You're reading the main text (building your current string).
- When you see a footnote marker (a number followed by '['), you save your place in the main text, note how many times to repeat the footnote, and start reading the footnote.
- When the footnote ends (']'), you repeat the footnote content the required number of times, go back to where you left off in the main text, and insert the repeated footnote.
We need to save two pieces of information when entering a bracket:
- The repeat count (the number before '[').
- The string we had built up before this bracket.
This is why we use two stacks:
- count_stack: stores the repeat count for each nesting level.
- string_stack: stores the accumulated string before each nesting level.
The algorithm processes one character at a time:
- Digit: Build the repeat count (handling multi-digit numbers by multiplying by 10 and adding).
- '[': Save current state (push count and current string to stacks), then reset both.
- ']': Pop from both stacks. The popped string is what came before this bracket group. The popped count tells us how many times to repeat our current string. Combine: previous_string + current_string × count.
- Letter: Simply append to the current string.
At the end, the current string holds the fully decoded result.
![Diagram showing two stacks (count_stack and string_stack) processing the encoded string 3[a2[c]] step by step](https://pub-a1b3030acfb94e84ba8a89fb182c53bc.r2.dev/public/394/two_stack_concept_v1.webp)
Step-by-Step Explanation
Let's trace through with s = "2[a3[b]]":
Step 1: Initialize: count_stack = [], string_stack = [], num = 0, current = "".
Step 2: Read s[0] = '2'. It's a digit.
- num = 0 × 10 + 2 = 2
- State: num=2, current="", count_stack=[], string_stack=[]
Step 3: Read s[1] = '['. Opening bracket.
- Push num=2 onto count_stack → [2]
- Push current="" onto string_stack → [""]
- Reset: num=0, current=""
- State: num=0, current="", count_stack=[2], string_stack=[""]
Step 4: Read s[2] = 'a'. It's a letter.
- current = "" + "a" = "a"
- State: num=0, current="a", count_stack=[2], string_stack=[""]
Step 5: Read s[3] = '3'. It's a digit.
- num = 0 × 10 + 3 = 3
- State: num=3, current="a", count_stack=[2], string_stack=[""]
Step 6: Read s[4] = '['. Opening bracket.
- Push num=3 onto count_stack → [2, 3]
- Push current="a" onto string_stack → ["", "a"]
- Reset: num=0, current=""
- State: num=0, current="", count_stack=[2, 3], string_stack=["", "a"]
Step 7: Read s[5] = 'b'. It's a letter.
- current = "" + "b" = "b"
- State: num=0, current="b", count_stack=[2, 3], string_stack=["", "a"]
Step 8: Read s[6] = ']'. Closing bracket.
- Pop count = 3 from count_stack → [2]
- Pop prev = "a" from string_stack → [""]
- current = "a" + "b" × 3 = "a" + "bbb" = "abbb"
- State: num=0, current="abbb", count_stack=[2], string_stack=[""]
Step 9: Read s[7] = ']'. Closing bracket.
- Pop count = 2 from count_stack → []
- Pop prev = "" from string_stack → []
- current = "" + "abbb" × 2 = "abbbabbb"
- State: num=0, current="abbbabbb", count_stack=[], string_stack=[]
Step 10: All characters processed. Return current = "abbbabbb".
Result: "abbbabbb"
Two-Stack Iterative Decoding — Processing "2[a3[b]]" — Watch how the count_stack and string_stack save and restore state at each bracket boundary, enabling us to decode nested patterns iteratively without recursion.
Algorithm
- Initialize two stacks: count_stack (for repeat counts) and string_stack (for accumulated strings).
- Initialize num = 0 (current repeat count) and current = "" (current string being built).
- Iterate through each character c in the input string:
- If c is a digit: num = num × 10 + digit (handles multi-digit numbers).
- If c is '[': push num onto count_stack, push current onto string_stack, reset num = 0 and current = "".
- If c is ']': pop count from count_stack, pop prev from string_stack. Set current = prev + current × count.
- If c is a letter: current = current + c.
- Return current as the fully decoded string.
Code
#include <string>
#include <stack>
using namespace std;
class Solution {
public:
string decodeString(string s) {
stack<int> countStack;
stack<string> stringStack;
int num = 0;
string current;
for (char c : s) {
if (isdigit(c)) {
// Build multi-digit number
num = num * 10 + (c - '0');
} else if (c == '[') {
// Save state and reset
countStack.push(num);
stringStack.push(current);
num = 0;
current = "";
} else if (c == ']') {
// Restore state and combine
int count = countStack.top(); countStack.pop();
string prev = stringStack.top(); stringStack.pop();
string repeated;
for (int i = 0; i < count; i++) {
repeated += current;
}
current = prev + repeated;
} else {
// Regular letter
current += c;
}
}
return current;
}
};class Solution:
def decodeString(self, s: str) -> str:
count_stack = []
string_stack = []
num = 0
current = ""
for c in s:
if c.isdigit():
# Build multi-digit number
num = num * 10 + int(c)
elif c == '[':
# Save state and reset
count_stack.append(num)
string_stack.append(current)
num = 0
current = ""
elif c == ']':
# Restore state and combine
count = count_stack.pop()
prev = string_stack.pop()
current = prev + current * count
else:
# Regular letter
current += c
return currentimport java.util.Deque;
import java.util.ArrayDeque;
class Solution {
public String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<String> stringStack = new ArrayDeque<>();
int num = 0;
StringBuilder current = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
// Build multi-digit number
num = num * 10 + (c - '0');
} else if (c == '[') {
// Save state and reset
countStack.push(num);
stringStack.push(current.toString());
num = 0;
current = new StringBuilder();
} else if (c == ']') {
// Restore state and combine
int count = countStack.pop();
String prev = stringStack.pop();
String repeated = current.toString();
current = new StringBuilder(prev);
for (int i = 0; i < count; i++) {
current.append(repeated);
}
} else {
// Regular letter
current.append(c);
}
}
return current.toString();
}
}Complexity Analysis
Time Complexity: O(n × m)
Where n is the length of the input string and m is the maximum length of the decoded output at any intermediate step. We iterate through each character of the input once, which is O(n). At each closing bracket, we perform string repetition and concatenation. The cost of these operations depends on the length of the intermediate strings and the repeat counts. In the worst case, the total work across all closing brackets is proportional to the output size.
Space Complexity: O(n + m)
The count_stack holds at most O(n) numbers (bounded by the number of bracket pairs). The string_stack holds intermediate strings whose combined size is bounded by O(m). The current string variable can grow up to O(m). Total: O(n + m). This is more memory-efficient than recursion because we avoid call stack frame overhead.