Decode String solution and explanation
9 more videos on this problem
Decode String - Leetcode 394 - PythonNeetCode · 16:26 · 144K views
LeetCode Decode String Solution Explained - JavaNick White · 10:52 · 63K views
Decode Strings (LeetCode 394) | Full solution with animations and examples | Study AlgorithmsNikhil Lohia · 14:40 · 61K views
Decode String 🔥 | Leetcode 394 | StackAyushi Sharma · 17:33 · 23K views
Decode String | Live Coding with Explanation | Leetcode #394Algorithms Made Easy · 6:14 · 14K views
LeetCode Solution - 394 Decode String | Google InterviewThinkFWD · 19:42 · 10K views
Decode String - LeetCode 394 - Python #leetcode #leetcode75 #stack #decode #stringDeepti Talesra · 7:59 · 4K views
Decode String | Leet code 394 | Theory explained + Python codeSai Anish Malla · 15:24 · 4K views
Stack - 14 | 394. Decode StringCTO Bhaiya · 37:39 · 1K views
LeetCode 394: Decode String C++ In Plain English (Google Interview)Algo Genius · 12:20 · 696 views
The problem
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.
def decode_string(s: str) -> str:
stack = []
current_str = ''
current_num = 0
for char in s:
if char.isdigit():
current_num = current_num * 10 + int(char)
elif char == '[':
stack.append((current_str, current_num))
current_str, current_num = '', 0
elif char == ']':
last_str, num = stack.pop()
current_str = last_str + current_str * num
else:
current_str += char
return current_str
# Example usage
s = "3[a2[c]]"
print(decode_string(s))import java.util.Stack;
public class DecodeString {
public static String decodeString(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<String> resultStack = new Stack<>();
String result = "";
int idx = 0;
while (idx < s.length()) {
if (Character.isDigit(s.charAt(idx))) {
int count = 0;
while (Character.isDigit(s.charAt(idx))) {
count = 10 * count + (s.charAt(idx) - '0');
idx++;
}
countStack.push(count);
} else if (s.charAt(idx) == '[') {
resultStack.push(result);
result = "";
idx++;
} else if (s.charAt(idx) == ']') {
StringBuilder temp = new StringBuilder(resultStack.pop());
int repeatTimes = countStack.pop();
while (repeatTimes-- > 0) {
temp.append(result);
}
result = temp.toString();
idx++;
} else {
result += s.charAt(idx++);
}
}
return result;
}
public static void main(String[] args) {
String s = "3[a2[c]]";
System.out.println(decodeString(s));
}
}#include <iostream>
#include <string>
#include <stack>
std::string decodeString(const std::string& s) {
std::stack<int> numStack;
std::stack<std::string> strStack;
std::string result = "";
int num = 0;
for (char c : s) {
if (isdigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '[') {
numStack.push(num);
strStack.push(result);
result = "";
num = 0;
} else if (c == ']') {
std::string temp = result;
int repeatTimes = numStack.top(); numStack.pop();
result = strStack.top(); strStack.pop();
while (repeatTimes--) result += temp;
} else {
result += c;
}
}
return result;
}
int main() {
std::string s = "3[a2[c]]";
std::cout << decodeString(s) << std::endl;
return 0;
}function decodeString(s) {
let numStack = [];
let strStack = [];
let currentStr = '';
let currentNum = 0;
for (let char of s) {
if (!isNaN(char)) {
currentNum = currentNum * 10 + Number(char);
} else if (char === '[') {
numStack.push(currentNum);
strStack.push(currentStr);
currentStr = '';
currentNum = 0;
} else if (char === ']') {
let repeatTimes = numStack.pop();
const lastStr = strStack.pop();
currentStr = lastStr + currentStr.repeat(repeatTimes);
} else {
currentStr += char;
}
}
return currentStr;
}
console.log(decodeString("3[a2[c]]"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* decodeString(char* s) {
int len = strlen(s), num = 0, top = -1, stCap = 100;
char* stack = (char*)malloc(stCap * sizeof(char));
char** resStack = (char**)malloc(stCap * sizeof(char*));
int* numStack = (int*)malloc(stCap * sizeof(int));
char* result = (char*)malloc(100 * sizeof(char));
int resLen = 0, resCap = 100;
for (int i = 0; i < len; i++) {
if (s[i] >= '0' && s[i] <= '9') {
num = num * 10 + (s[i] - '0');
} else if (s[i] == '[') {
numStack[++top] = num;
resStack[top] = (char*)malloc((resCap+1) * sizeof(char));
strcpy(resStack[top], result);
resLen = 0;
num = 0;
} else if (s[i] == ']') {
char* temp = (char*)malloc((resCap+1) * sizeof(char));
strcpy(temp, result);
for (int j = 0; j < numStack[top]; j++) {
for (int k = 0; k < resLen; k++) {
result[resLen * j + k] = temp[k];
}
}
result[resLen * numStack[top]] = '\0';
resLen *= numStack[top]; // Update current length
sprintf(result, "%s%s", resStack[top--], result); // Add previous result from stack
free(temp);
} else {
result[resLen++] = s[i];
if (resLen == resCap) {
resCap *= 2;
result = (char*)realloc(result, resCap * sizeof(char));
}
}
}
return result;
}
int main() {
char s[] = "3[a2[c]]";
printf("%s\n", decodeString(s));
return 0;
}using System;
using System.Collections.Generic;
class DecodeStringClass {
public static string DecodeString(string s) {
Stack<int> countStack = new Stack<int>();
Stack<string> resultStack = new Stack<string>();
string result = "";
int index = 0;
while (index < s.Length) {
if (char.IsDigit(s[index])) {
int count = 0;
while (char.IsDigit(s[index])) {
count = count * 10 + (s[index] - '0');
index++;
}
countStack.Push(count);
} else if (s[index] == '[') {
resultStack.Push(result);
result = "";
index++;
} else if (s[index] == ']') {
string temp = resultStack.Pop();
int repeatTimes = countStack.Pop();
for (int i = 0; i < repeatTimes; i++) {
temp += result;
}
result = temp;
index++;
} else {
result += s[index];
index++;
}
}
return result;
}
static void Main(string[] args) {
string s = "3[a2[c]]";
Console.WriteLine(DecodeString(s));
}
}In this Python solution, a stack is used to maintain state information as we encounter new nested encoding structures. Each digit is multiplier, '[' signals the capturing of a prev state, and ']' denotes expanding the captured state, building the decoded string progressively as either digits or character sequences appear.
Time Complexity: O(n), since each character is processed once until the whole string is decoded.
Space Complexity: O(n), given the potential storage requirements of active nested structures.
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.
def decode_string(s: str) -> str:
def decode_helper(i):
result = ''
while i < len(s) and s[i] != ']':
if not s[i].isdigit():
result += s[i]
i += 1
else:
k = 0
while i < len(s) and s[i].isdigit():
k = k * 10 + int(s[i])
i += 1
i += 1 # skip the '['
decoded_part, i = decode_helper(i)
i += 1 # skip the ']'
result += decoded_part * k
return result, i
return decode_helper(0)[0]
# Example usage
s = "3[a2[c]]"
print(decode_string(s))class DecodeString {
public String decodeString(String s) {
return decodeHelper(s, new int[]{0});
}
private String decodeHelper(String s, int[] i) {
StringBuilder result = new StringBuilder();
while (i[0] < s.length() && s.charAt(i[0]) != ']') {
if (!Character.isDigit(s.charAt(i[0]))) {
result.append(s.charAt(i[0]++));
} else {
int k = 0;
while (i[0] < s.length() && Character.isDigit(s.charAt(i[0]))) {
k = k * 10 + s.charAt(i[0]++) - '0';
}
i[0]++; // skipping the '['
String decodedString = decodeHelper(s, i);
i[0]++; // skipping the ']'
while (k-- > 0) result.append(decodedString);
}
}
return result.toString();
}
public static void main(String[] args) {
DecodeString ds = new DecodeString();
String s = "3[a2[c]]";
System.out.println(ds.decodeString(s));
}
}#include <iostream>
#include <string>
class Solution {
public:
std::string decodeString(const std::string &s, int &i) {
std::string result = "";
while (i < s.length() && s[i] != ']') {
if (!isdigit(s[i])) {
result += s[i++];
} else {
int n = 0;
while (i < s.length() && isdigit(s[i])) {
n = n * 10 + s[i++] - '0';
}
i++; // skipping the '['
std::string decodedString = decodeString(s, i);
i++; // skipping the ']'
while (n-- > 0) result += decodedString;
}
}
return result;
}
std::string decodeString(const std::string &s) {
int i = 0;
return decodeString(s, i);
}
};
int main() {
Solution sol;
std::string s = "3[a2[c]]";
std::cout << sol.decodeString(s) << std::endl;
return 0;
}function decodeString(s) {
const decodeHelper = (i) => {
let result = '';
while (i < s.length && s[i] !== ']') {
if (!isNaN(s[i])) {
let num = 0;
while (!isNaN(s[i])) {
num = num * 10 + parseInt(s[i], 10);
i++;
}
i++; // skip the '['
let [decodedString, newIndex] = decodeHelper(i);
i = newIndex + 1; // skip the ']'
result += decodedString.repeat(num);
} else {
result += s[i];
i++;
}
}
return [result, i];
}
return decodeHelper(0)[0];
}
console.log(decodeString("3[a2[c]]"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *decodeStringHelper(const char *s, int *i) {
int len = strlen(s);
char *result = (char*)malloc(1000 * sizeof(char));
int resultLen = 0, resultCap = 1000;
while (*i < len && s[*i] != ']') {
if (!isdigit(s[*i])) {
if (resultLen + 1 >= resultCap) {
resultCap *= 2;
result = realloc(result, resultCap * sizeof(char));
}
result[resultLen++] = s[*i];
(*i)++;
} else {
int k = 0;
while (*i < len && isdigit(s[*i])) {
k = k * 10 + s[*i] - '0';
(*i)++;
}
(*i)++; // Skipping '['
char *decodedString = decodeStringHelper(s, i);
(*i)++; // Skipping ']'
for (int j = 0; j < k; j++) {
for (int l = 0; l < strlen(decodedString); l++) {
if (resultLen + 1 >= resultCap) {
resultCap *= 2;
result = realloc(result, resultCap * sizeof(char));
}
result[resultLen++] = decodedString[l];
}
}
free(decodedString);
}
}
result[resultLen] = '\0';
return result;
}
char *decodeString(char *s) {
int i = 0;
return decodeStringHelper(s, &i);
}
int main() {
char s[] = "3[a2[c]]";
printf("%s\n", decodeString(s));
return 0;
}using System;
using System.Text;
class DecodeStringClass {
public static string DecodeString(string s) {
return DecodeHelper(s, new int[] { 0 });
}
private static string DecodeHelper(string s, int[] i) {
StringBuilder result = new StringBuilder();
while (i[0] < s.Length && s[i[0]] != ']') {
if (!Char.IsDigit(s[i[0]])) {
result.Append(s[i[0]]);
i[0]++;
} else {
int num = 0;
while (i[0] < s.Length && Char.IsDigit(s[i[0]])) {
num = num * 10 + s[i[0]] - '0';
i[0]++;
}
i[0]++; // Skip '['
string subResult = DecodeHelper(s, i);
i[0]++; // Skip ']'
while (num-- > 0) {
result.Append(subResult);
}
}
}
return result.ToString();
}
static void Main(string[] args) {
string s = "3[a2[c]]";
Console.WriteLine(DecodeString(s));
}
}This Python solution uses recursion to manage nested pattern expansions. As each '[' appears, recursion enters further depth, resolving encoded sub-facets upon reaching ']', allowing unfolding as it returns, thus appending expanded substrings to the growing decoded output.
Time Complexity: O(n), where n covers total string length through recursive parsing.
Space Complexity: O(n), mirrored by recursive call depth efficacious for intricate nesting scenarios.
Approach 3: Default Approach
function decodeString(s: string): string {
let ans = '';
let stack = [];
let count = 0; // repeatCount
for (let cur of s) {
if (/[0-9]/.test(cur)) {
count = count * 10 + Number(cur);
} else if (/[a-z]/.test(cur)) {
ans += cur;
} else if ('[' == cur) {
stack.push([ans, count]);
// reset
ans = '';
count = 0;
} else {
// match ']'
let [pre, count] = stack.pop();
ans = pre + ans.repeat(count);
}
}
return ans;
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-Based Iterative Decoding | Time Complexity: O(n), since each character is processed once until the whole string is decoded. |
| Recursive Decoding Approach | Time Complexity: O(n), where n covers total string length through recursive parsing. |
| Default Approach | – |
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. |
Frequently asked questions
Is Decode String easy or hard?
Decode String is usually classified as a medium difficulty problem. The challenge comes from correctly handling nested brackets and repeat counts, but once you apply a stack or recursive parsing strategy, the implementation becomes straightforward.
Decode String Python/Java solution
In Python or Java, the typical solution uses a stack of pairs storing the previous string and repeat count. As the algorithm scans the input, it builds numbers, pushes state at '[', and reconstructs the string when ']' appears. Both languages achieve O(n) time with O(n) space.
How to solve Decode String in O(n)?
Use a stack to track the current string and repetition count whenever an opening bracket appears. Build numbers for repeat counts, append characters normally, and when a closing bracket is encountered, pop the previous state and append the repeated substring. Each character is handled once, leading to O(n) time.
What is the best approach for Decode String?
The stack-based iterative approach is generally considered the best solution. It processes the string in one pass while storing previous states (current string and repeat count) on a stack whenever a new bracket level starts. This guarantees O(n) time complexity and handles nested patterns cleanly.
Is Decode String asked at Google/Amazon/Meta?
Decode String is a common medium-level string and stack problem frequently reported in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of stacks, recursion, and parsing nested structures.
What data structure is used in Decode String?
The most common data structure is a stack. It stores previous partial strings and repetition counts when entering nested brackets. Recursive implementations rely on the call stack instead of an explicit stack structure.
What is the time complexity of Decode String?
The optimal solutions run in O(n) time, where n is the length of the input string. Each character is processed once while building the decoded output. Space complexity is also O(n) because stacks or recursion frames store intermediate substrings and counts.