Decode String

LeetCode 394: Decode String Solution & Explanation

Problem Overview

TL;DR: Iterate through the string maintaining a stack to store partial strings and repeat counts, pushing context when entering brackets and popping to combine results when exiting them.

The Decode String problem asks us to expand a compressed string format. The input string contains patterns like k[encoded_string], which signifies that the encoded_string should be repeated exactly k times. These patterns can be nested, such as 3[a2[c]]. Our goal is to return the fully expanded string. This is a popular interview question that tests your ability to handle nested structures and parsing logic.

Brute Force Approach for Decode String

A naive approach to solving LeetCode 394 involves repeatedly scanning the string to resolve the innermost brackets one by one.

The algorithm works as follows:

1. Search the string for the first closing bracket ].
2. From that position, scan backwards to find the nearest opening bracket [.
3. Extract the number k immediately preceding the [.
4. Replace the substring k[...] with the content inside the brackets repeated k times.
5. Repeat this process until no brackets remain in the string.

Pseudo-code

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.

Algorithm Strategy: Stack Patterns

We will use two stacks (or a single stack storing objects) to simulate the decoding process: one for counts (countStack) and one for strings (stringStack). We also maintain two variables: currentString (to build the current segment) and k (to build the current repeat number).

1. Iterate through the input string character by character.
2. Case 1: Digit. If the character is a digit, update k. Since numbers can have multiple digits (e.g., 12), we calculate k = k * 10 + digit.
3. Case 2: Opening Bracket [. This implies the start of a new encoded section.
   • Push the currentString onto stringStack.
   • Push the calculated k onto countStack.
   • Reset currentString to empty and k to 0.
4. Case 3: Closing Bracket ]. This implies the end of the current encoded section.
   • Pop the repeat count currentK from countStack.
   • Pop the previousString from stringStack.
   • Update currentString by decoding: currentString = previousString + (currentString repeated currentK times).
5. Case 4: Letter. Simply append the character to currentString.
6. Return currentString after the loop finishes.

This strategy ensures that currentString always holds the fully decoded content of the current nesting level.

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.

Pattern Reuse Notes

The Stack - Simulation / Backtracking Helper pattern is highly versatile. Understanding how to use a stack to maintain "parent" state while processing "child" state is crucial for several other problems:

• LeetCode 71: Simplify Path: Uses a stack to process directory components, pushing valid names and popping on .. to simulate directory navigation.
• LeetCode 735: Asteroid Collision: Uses a stack to simulate the state of stable asteroids. Collisions (nested interactions) are resolved by popping from the stack until a stable state is reached.

Reference Implementation

C++ Solution for LeetCode 394

1#include <iostream>
2#include <string>
3#include <stack>
4#include <cctype>
5
6class Solution {
7public:
8    string decodeString(string s) {
9        std::stack<int> countStack;
10        std::stack<std::string> stringStack;
11        std::string currentString = "";
12        int k = 0;
13
14        for (char ch : s) {
15            if (isdigit(ch)) {
16                // Build the number k (handles multi-digit numbers)
17                k = k * 10 + (ch - '0');
18            } else if (ch == '[') {
19                // Push current context to stacks
20                countStack.push(k);
21                stringStack.push(currentString);
22                // Reset context for the inner bracket
23                currentString = "";
24                k = 0;
25            } else if (ch == ']') {
26                // Decode current level
27                std::string decodedString = stringStack.top();
28                stringStack.pop();
29                
30                int currentK = countStack.top();
31                countStack.pop();
32                
33                // Append the current string k times
34                for (int i = 0; i < currentK; i++) {
35                    decodedString += currentString;
36                }
37                currentString = decodedString;
38            } else {
39                // Regular character
40                currentString += ch;
41            }
42        }
43
44        return currentString;
45    }
46};

Java Solution for LeetCode 394

1import java.util.Stack;
2
3class Solution {
4    public String decodeString(String s) {
5        Stack<Integer> countStack = new Stack<>();
6        Stack<StringBuilder> stringStack = new Stack<>();
7        StringBuilder currentString = new StringBuilder();
8        int k = 0;
9
10        for (char ch : s.toCharArray()) {
11            if (Character.isDigit(ch)) {
12                k = k * 10 + (ch - '0');
13            } else if (ch == '[') {
14                countStack.push(k);
15                stringStack.push(currentString);
16                currentString = new StringBuilder();
17                k = 0;
18            } else if (ch == ']') {
19                StringBuilder decodedString = stringStack.pop();
20                int currentK = countStack.pop();
21                
22                // Append currentString repeated currentK times to the popped string
23                for (int i = 0; i < currentK; i++) {
24                    decodedString.append(currentString);
25                }
26                currentString = decodedString;
27            } else {
28                currentString.append(ch);
29            }
30        }
31
32        return currentString.toString();
33    }
34}

Python Solution for LeetCode 394

1class Solution:
2    def decodeString(self, s: str) -> str:
3        stack = []
4        current_string = ""
5        k = 0
6        
7        for char in s:
8            if char.isdigit():
9                k = k * 10 + int(char)
10            elif char == "[":
11                # Push the tuple (current_string, k) onto the stack
12                stack.append((current_string, k))
13                # Reset for the new context
14                current_string = ""
15                k = 0
16            elif char == "]":
17                # Pop the last context
18                prev_string, prev_k = stack.pop()
19                current_string = prev_string + (current_string * prev_k)
20            else:
21                current_string += char
22                
23        return current_string