Log inSign up
mediumleetcodeNot Started

Decode String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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].

Example 1 · Example:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Explanation: 3 * "a" + 2 * "bc" = "aaabcbc"

Example 2 · Example:

Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: Inner 2[c] -> "cc", then 3[acc] -> "accaccacc"

Example 3 · Example:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Explanation: 2 * "abc" + 3 * "cd" + "ef" = "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].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Learn state management across nested scopes using stack frames.
  • Correctly parse multi-digit numbers from character streams.
  • Implement both iterative two-stack and recursive parsing solutions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever matching delimiters (like brackets) enclose expressions with localized multiplier scopes.
  • When inner sub-expressions must be resolved before outer ones.

Algorithmic Decision Tree:

  • Parentheses / Bracket Stack Matching
  • Recursive Descent Parsing

Connected Patterns:

Basic CalculatorParse Lisp ExpressionMini ParserScore of Parentheses

1. Single Character Stack Simulation

Intuition

Iterate character by character. Push characters onto stack until ] is encountered. Pop characters until [ to extract the target substring. Then pop preceding digits to form the number k. Repeat the substring k times and push back onto the stack. At the end, join everything in the stack.

When to apply: When conceptualizing the problem strictly as stack-based replacement.

Algorithm

  1. Create a stack of characters or strings.
  2. Iterate through the string: if char != ], push to stack.
  3. If char == ], pop characters until [ into a temporary string segment.
  4. Pop the [ bracket.
  5. Pop consecutive digit characters and calculate multiplier k.
  6. Repeat segment k times and push the result back onto the stack.
  7. After processing all characters, join all stack items.

Single Character Stack Simulation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, [, a, 2, [, c, ], ]]
Current operationSTEP 1 OF 6
Observation: Push tokens onto stack until index 6 (']')
Visual state
Values and pointers at this exact step
array
S
3
[
a
2
[
c
]
]
0
1
2
3
4
5
6
↑ FIRST CLOSING BRACKET ']'
7
Variables at this step
stack
["3","[","a","2","[","c"]
currentChar
]
Check / comparison
Push chars '3', '[', 'a', '2', '[', 'c' onto stack until encountering ']'.
Decision / next transition
Encounter ']': trigger unrolling of innermost bracketed subproblem.
Why this step matters

Observation: Push tokens onto stack until index 6 (']').

Decision: Stack contains ['3', '[', 'a', '2', '[', 'c']. Stop pushing and pop backwards until '['.

Invariant: The first encountered ']' always corresponds to the most deeply nested expression.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 std::string decodeString(std::string s) {
9 std::vector<std::string> st;
10 int i = 0;
11 while (i < (int)s.size()) {
12 if (s[i] != ']') {
13 st.push_back(std::string(1, s[i]));
14 i++;
15 } else {
16 std::string sub = "";
17 while (!st.empty() && st.back() != "[") {
18 sub = st.back() + sub;
19 st.pop_back();
20 }
21 st.pop_back(); // remove __SF_TOKEN_A__
22
23 std::string numStr = "";
24 while (!st.empty() && isdigit(st.back()[0])) {
25 numStr = st.back() + numStr;
26 st.pop_back();
27 }
28 int k = std::stoi(numStr);
29 std::string repeated = "";
30 while (k--) repeated += sub;
31 st.push_back(repeated);
32 i++;
33 }
34 }
35 std::string res = "";
36 for (const auto& str : st) res += str;
37 return res;
38 }
39};
40
41int main() {
42 Solution sol;
43 std::cout << sol.decodeString("3[a2[c]]") << std::endl; // "accaccacc"
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(Max Output Length) — Every character in the final decoded string is created and pushed onto stack.
  • Space complexity: O(Max Output Length)

Why Brute Force Doesn't Scale:

Using two explicit stacks avoids function call overhead and recursion limit issues.

Using StringBuilder in Java / reserving vector capacity avoids repeated allocations.

2. Recursive Descent Parsing

Intuition

Maintain a shared index pointer. At each recursion level, parse characters into a current string builder. If a digit is seen, update multiplier k. If [ is encountered, advance index and recursively call helper to decode the nested subproblem, then multiply the returned substring by k and append. If ] is seen, return current result.

When to apply: When aiming for recursive grammar parsing elegance.

Algorithm

  1. Pass string s and a mutable pointer/index to recursive function helper.
  2. While index < length and s[index] != ]:
  3. If digit: k = k * 10 + (s[index] - '0').
  4. If [: increment index, call helper to get nestedStr, append nestedStr k times, reset k = 0.
  5. If letter: append char to current buffer.
  6. If ]: advance index and break loop to return buffer.
  7. Return the final decoded string.

Recursive Descent Parsing

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, [, a, 2, [, c, ], ]]
Current operationSTEP 1 OF 6
Observation: Root call reads multiplier $k = 3$
Visual state
Values and pointers at this exact step
array
S
3
[
a
2
[
c
]
]
0
↑ FRAME 0: k=3
1
2
3
4
5
6
7
Variables at this step
frame
0
k
3
callStackDepth
1
Check / comparison
Frame 0 parses k = 3, encounters '[' at idx 1.
Decision / next transition
Spawn recursive call decode(idx=2).
Why this step matters

Observation: Root call reads multiplier k = 3. Encounter '[' at index 1.

Decision: Push frame onto call stack and recursively decode inner expression starting at index 2.

Invariant: Call stack replaces explicit data structure stack.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5 std::string decodeHelper(const std::string& s, int& idx) {
6 std::string result = "";
7 int k = 0;
8 while (idx < (int)s.size()) {
9 char c = s[idx++];
10 if (isdigit(c)) {
11 k = k * 10 + (c - '0');
12 } else if (c == '[') {
13 std::string nested = decodeHelper(s, idx);
14 while (k > 0) {
15 result += nested;
16 k--;
17 }
18 } else if (c == ']') {
19 break;
20 } else {
21 result.push_back(c);
22 }
23 }
24 return result;
25 }
26public:
27 std::string decodeString(std::string s) {
28 int idx = 0;
29 return decodeHelper(s, idx);
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << sol.decodeString("3[a]2[bc]") << std::endl; // "aaabcbc"
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(Max Output Length) — Recursion depth is proportional to bracket nesting level.
  • Space complexity: O(Max Nesting Depth) call stack

3. Two Stacks Iterative Approach (Count & String Stack)

Intuition

Maintain currentString and currentK. When encountering a digit, update currentK = currentK * 10 + digit. When encountering [, push currentK to countStack and currentString to stringStack, then reset currentK = 0 and currentString = "". When encountering ], pop k and prevString, then set currentString = prevString + currentString.repeat(k). For standard letters, append to currentString.

When to apply: Standard production pattern for parsing nested string structures without recursion depth limits.

Algorithm

  1. Initialize countStack, stringStack, currentK = 0, currentString = "".
  2. Iterate character c in s:
  3. Case 1 (digit): currentK = currentK * 10 + (c - '0').
  4. Case 2 ([): Push currentK to countStack, push currentString to stringStack. Reset currentK = 0, currentString = "".
  5. Case 3 (]): Pop multiplier count and previous string prevStr. Set currentString = prevStr + repeat(currentString, count).
  6. Case 4 (letter): Append c to currentString.
  7. Return currentString.

Dual Stack Nested Bracket Expansion

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, [, a, 2, [, c, ], ]]
Current operationSTEP 1 OF 6
Observation: Read digit '3'
Visual state
Values and pointers at this exact step
array
S
3
[
a
2
[
c
]
]
0
↑ Read multiplier: 3
1
2
3
4
5
6
7
Variables at this step
currentNum
3
currentStr
countStack
[]
stringStack
[]
Why this step matters

Observation: Read digit '3'. Accumulate multiplier: currentNum = 3.

Decision: Store incoming multiplier.

Invariant: Numbers precede bracketed substrings.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <stack>
4
5class Solution {
6public:
7 std::string decodeString(std::string s) {
8 std::stack<int> countStack;
9 std::stack<std::string> stringStack;
10 std::string currentString = "";
11 int currentK = 0;
12
13 for (char c : s) {
14 if (isdigit(c)) {
15 currentK = currentK * 10 + (c - '0');
16 } else if (c == '[') {
17 countStack.push(currentK);
18 stringStack.push(currentString);
19 currentK = 0;
20 currentString = "";
21 } else if (c == ']') {
22 int repeatCount = countStack.top();
23 countStack.pop();
24 std::string prevString = stringStack.top();
25 stringStack.pop();
26
27 std::string expanded = "";
28 while (repeatCount > 0) {
29 expanded += currentString;
30 repeatCount--;
31 }
32 currentString = prevString + expanded;
33 } else {
34 currentString.push_back(c);
35 }
36 }
37
38 return currentString;
39 }
40};
41
42int main() {
43 Solution sol;
44 std::cout << sol.decodeString("3[a2[c]]") << std::endl; // "accaccacc"
45 std::cout << sol.decodeString("2[abc]3[cd]ef") << std::endl; // "abcabccdcdcdef"
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(Max Output Length) — Iterates through the string once, and each output character is constructed and appended linearly.
  • Space complexity: O(Max Output Length)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Descent ParsingO(Max Output Length)O(Max Nesting Depth)Clean mathematical modeling of grammar rules.Requires tracking global index pointer across recursive calls.
2.Single Character StackO(Output Length)O(Output Length)Pushes every character including brackets, pops back to [ on ].More string allocations when parsing numbers backward from stack.
3.Two Explicit Stacks (Count & String)OptimalO(Output Length)O(Output Length)Highly intuitive, separates number parsing from string building, industry favorite.Maintains two stack data structures.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating single digit multiplier only (not multiplying by 10 on next digit).

Pitfall 2:

Not clearing currentK or currentString on encountering [.

Crucial Edge Cases to Validate:

  • Multi-digit multipliers (e.g., 12[a]): Using currentK = currentK * 10 + digit correctly handles any number of digits.
  • No brackets present (e.g., abc): Characters are simply appended to currentString without any stack operations.
  • Consecutive bracket groups (e.g., 2[a]3[b]): First group finishes into currentString aa, then 3[ pushes aa as prevString.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always clarify multi-digit numbers upfront to show thoroughness.
  2. State both stack and recursive formulations to showcase breadth of pattern mastery.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we push currentString to stringStack when encountering [?

Back to DSA Sheet