394. Decode String - Explanation

Description

You are given an encoded string s, 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. There will not be input like 3a, 2[4], a[a] or a[2].

The test cases are generated so that the length of the output will never exceed 100,000.

Example 1:

Input: s = "2[a3[b]]c"

Output: "abbbabbbc"

Example 2:

Input: s = "axb3[z]4[c]"

Output: "axbzzzcccc"

Example 3:

Input: s = "ab2[c]3[d]1[x]"

Output: "abccdddx"

Constraints:

1 <= s.length <= 30
s is made up of lowercase English letters, digits, and square brackets '[]'.
All the integers in s are in the range [1, 300].
s is guaranteed to be a valid input.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

The encoded string has a nested structure where patterns like k[encoded_string] can contain other encoded patterns inside. This naturally maps to recursion. When we encounter an opening bracket, we recursively decode the inner content, then repeat it k times. The recursion handles arbitrary nesting depth automatically.

Algorithm

Maintain a global index i to track the current position in the string.
Define a recursive helper function:
- Initialize an empty result string and a multiplier k = 0.
- While i is within bounds:
  - If the current character is a digit, update k by shifting left and adding the digit.
  - If it's [, increment i and recursively decode the inner string. Multiply the result by k and append it. Reset k to 0.
  - If it's ], return the current result (end of this level).
  - Otherwise, append the character to the result.
  - Increment i after each iteration.
- Return the result.
Call the helper function and return its result.

class Solution:
    def decodeString(self, s: str) -> str:
        self.i = 0

        def helper():
            res = ""
            k = 0

            while self.i < len(s):
                c = s[self.i]

                if c.isdigit():
                    k = k * 10 + int(c)
                elif c == "[":
                    self.i += 1
                    res += k * helper()
                    k = 0
                elif c == "]":
                    return res
                else:
                    res += c

                self.i += 1
            return res

        return helper()

Time & Space Complexity

Time complexity: $O(n + N)$
Space complexity: $O(n + N)$

Where $n$ is the length of the input string and $N$ is the length of the output string.

2. One Stack

Intuition

We can convert the recursive approach to an iterative one using a single stack. Push every character onto the stack until we hit a closing bracket ]. At that point, pop characters to extract the substring inside the brackets, then pop the digits to get the repeat count k. Multiply the substring and push the result back onto the stack. This simulates the recursive call stack.

Algorithm

Initialize an empty stack.
Iterate through each character in the string:
- If the character is not ], push it onto the stack.
- If it is ]:
  - Pop characters until [ is found to build the substring.
  - Pop [ from the stack.
  - Pop all consecutive digits to form the repeat count k.
  - Repeat the substring k times and push the result back onto the stack.
After processing all characters, join the stack contents to form the final decoded string.

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []

        for i in range(len(s)):
            if s[i] != "]":
                stack.append(s[i])
            else:
                substr = ""
                while stack[-1] != "[":
                    substr = stack.pop() + substr
                stack.pop()

                k = ""
                while stack and stack[-1].isdigit():
                    k = stack.pop() + k
                stack.append(int(k) * substr)

        return "".join(stack)

Time & Space Complexity

Time complexity: $O(n + N ^ 2)$
Space complexity: $O(n + N)$

Where $n$ is the length of the input string and $N$ is the length of the output string.

3. Two Stacks

Intuition

Using two separate stacks provides cleaner logic: one stack for accumulated strings and another for repeat counts. When we see [, we save the current string and count, then start fresh. When we see ], we pop the previous string and count, repeat the current string, and concatenate. This approach avoids the overhead of extracting digits and substrings from a mixed stack.

Algorithm

Initialize two stacks: one for strings (stringStack) and one for counts (countStack).
Maintain a current string cur and a current multiplier k.
Iterate through each character:
- If it's a digit, update k = k * 10 + digit.
- If it's [, push cur and k onto their respective stacks, then reset cur to empty and k to 0.
- If it's ], pop the previous string and count. Set cur to the popped string plus the current string repeated by the popped count.
- Otherwise, append the character to cur.
Return cur as the final decoded string.

class Solution:
    def decodeString(self, s: str) -> str:
        string_stack = []
        count_stack = []
        cur = ""
        k = 0

        for c in s:
            if c.isdigit():
                k = k * 10 + int(c)
            elif c == "[":
                string_stack.append(cur)
                count_stack.append(k)
                cur = ""
                k = 0
            elif c == "]":
                temp = cur
                cur = string_stack.pop()
                count = count_stack.pop()
                cur += temp * count
            else:
                cur += c

        return cur

Time & Space Complexity

Time complexity: $O(n + N)$
Space complexity: $O(n + N)$

Where $n$ is the length of the input string and $N$ is the length of the output string.

Common Pitfalls

Multi-Digit Numbers

The repeat count k can be more than one digit (e.g., "12[a]" means repeat 'a' 12 times). A common mistake is treating only single digits.

# Wrong: only handles single digit
k = int(s[i])

# Correct: accumulate all digits
k = k * 10 + int(s[i])

Not Resetting the Repeat Count

After processing a [, the repeat count k must be reset to 0 for the next pattern. Forgetting this causes incorrect multiplications in nested structures.

# Wrong: k carries over to next pattern
if c == "[":
    self.i += 1
    res += k * helper()
    # Missing: k = 0

# Correct: reset k after using it
if c == "[":
    self.i += 1
    res += k * helper()
    k = 0

Index Management in Recursion

When using recursion with a shared index, incrementing i at the wrong time causes characters to be skipped or processed twice. The index should be incremented after processing [ but before the recursive call.

# Wrong: skips the character after [
if c == "[":
    res += k * helper()
    self.i += 1  # Too late!

# Correct: increment before recursive call
if c == "[":
    self.i += 1
    res += k * helper()