Pseudo-code

text
while string contains '[':
    find first ']' at index right
    find matching '[' at index left before right
    extract number k before left
    content = substring(left+1, right)
    expanded = repeat content k times
    string = string.prefix + expanded + string.suffix
return string

Complexity and Failure Analysis

• Time Complexity: This approach can be highly inefficient. In the worst case, finding brackets and performing string concatenation (which requires shifting characters) repeatedly leads to a complexity closer to $O(N \cdot L)$, where $N$ is the input length and $L$ is the max output length.
• Why it fails: While the input constraints for s are small ($30$), the output length can be up to $10^5$. Repeatedly reconstructing the entire string for every nested layer creates unnecessary overhead. Furthermore, implementing the parsing logic to correctly identify k and handle string splicing manually is error-prone during an interview.

Core Insight for Decode String

The key intuition for the optimal LeetCode 394 solution is to treat the string parsing as a simulation of a recursive process using an explicit stack.

When we traverse the string and encounter an opening bracket [, we are effectively entering a new "scope" or "frame." We need to remember two things from the current scope before we dive deeper:

1. The number of times the upcoming segment should be repeated (k).
2. The string we have built so far in the current scope (currentString).

We push these values onto a stack. When we encounter a closing bracket ], it signals the end of the current scope. We can then pop the previous scope's data from the stack and combine it with the result of the current scope.

This approach enforces the invariant that the top of the stack always contains the context of the immediate parent of the current bracket expression. By maintaining this invariant, we ensure that deeply nested strings are decoded first and correctly appended to their outer layers.

Visual Description: Imagine traversing the string 3[a2[c]].

1. We read 3, then [. We push our current state to the stack and reset.
2. We read a, then 2, then [. We push the state (holding a) to the stack and reset again.
3. We read c, then ]. We resolve the current level: repeat c 2 times (cc). We pop the stack to retrieve a, appending cc to it (acc).
4. We read the final ]. We resolve the level: repeat acc 3 times.

Execution Flow

Let's trace the algorithm with input: 3[a2[c]]

1. Initialize: countStack = [], stringStack = [], currentString = "", k = 0.
2. Process '3':
   • It's a digit. k becomes 3.
3. Process '[':
   • Push currentString ("") to stringStack.
   • Push k (3) to countStack.
   • Reset currentString = "", k = 0.
   • Stacks: stringStack=[""], countStack=[3]
4. Process 'a':
   • It's a letter. currentString becomes "a".
5. Process '2':
   • It's a digit. k becomes 2.
6. Process '[':
   • Push currentString ("a") to stringStack.
   • Push k (2) to countStack.
   • Reset currentString = "", k = 0.
   • Stacks: stringStack=["", "a"], countStack=[3, 2]
7. Process 'c':
   • It's a letter. currentString becomes "c".
8. Process ']':
   • Pop currentK (2) from countStack.
   • Pop prevString ("a") from stringStack.
   • currentString becomes prevString + (currentString * currentK)
   • currentString = "a" + ("c" * 2) = "acc".
   • Stacks: stringStack=[""], countStack=[3]
9. Process ']':
   • Pop currentK (3) from countStack.
   • Pop prevString ("") from stringStack.
   • currentString becomes "" + ("acc" * 3) = "accaccacc".
   • Stacks: Empty.
10. End: Return "accaccacc".

Proof of Correctness

The correctness of this algorithm relies on the stack invariant: the stack always stores the valid state of the outer context while the inner context is being processed.

When we encounter a ], the currentString variable holds the correct decoded value for the innermost expression. The top of stringStack holds the prefix that appeared before this expression, and the top of countStack holds the multiplier for this expression. By combining pop(stringStack) + currentString * pop(countStack), we correctly reconstruct the string at that specific nesting depth. By induction, since the base case (no brackets) is handled correctly by simple appending, and each reduction step correctly merges an inner scope into an outer scope, the final result is correct.

Reference Implementation

C++ Solution for LeetCode 394

cpp
#include <iostream>
#include <string>
#include <stack>
#include <cctype>

class Solution {
public:
    string decodeString(string s) {
        std::stack<int> countStack;
        std::stack<std::string> stringStack;
        std::string currentString = "";
        int k = 0;

        for (char ch : s) {
            if (isdigit(ch)) {
                // Build the number k (handles multi-digit numbers)
                k = k * 10 + (ch - '0');
            } else if (ch == '[') {
                // Push current context to stacks
                countStack.push(k);
                stringStack.push(currentString);
                // Reset context for the inner bracket
                currentString = "";
                k = 0;
            } else if (ch == ']') {
                // Decode current level
                std::string decodedString = stringStack.top();
                stringStack.pop();
                
                int currentK = countStack.top();
                countStack.pop();
                
                // Append the current string k times
                for (int i = 0; i < currentK; i++) {
                    decodedString += currentString;
                }
                currentString = decodedString;
            } else {
                // Regular character
                currentString += ch;
            }
        }

        return currentString;
    }
};

Java Solution for LeetCode 394

java
import java.util.Stack;

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                k = k * 10 + (ch - '0');
            } else if (ch == '[') {
                countStack.push(k);
                stringStack.push(currentString);
                currentString = new StringBuilder();
                k = 0;
            } else if (ch == ']') {
                StringBuilder decodedString = stringStack.pop();
                int currentK = countStack.pop();
                
                // Append currentString repeated currentK times to the popped string
                for (int i = 0; i < currentK; i++) {
                    decodedString.append(currentString);
                }
                currentString = decodedString;
            } else {
                currentString.append(ch);
            }
        }

        return currentString.toString();
    }
}

Python Solution for LeetCode 394

python
class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        current_string = ""
        k = 0
        
        for char in s:
            if char.isdigit():
                k = k * 10 + int(char)
            elif char == "[":
                # Push the tuple (current_string, k) onto the stack
                stack.append((current_string, k))
                # Reset for the new context
                current_string = ""
                k = 0
            elif char == "]":
                # Pop the last context
                prev_string, prev_k = stack.pop()
                current_string = prev_string + (current_string * prev_k)
            else:
                current_string += char
                
        return current_string

Why does the stack approach use currentString = "" after pushing?

Mistake: Forgetting to reset currentString or k after pushing to the stack. Why: Once you enter a bracket [, you are starting a fresh context. The old context is saved on the stack. Consequence: If you don't reset, the inner bracket processing will inherit "stale" data from the outer bracket, leading to duplicated or malformed strings.