LeetCode Problem 394

Difficulty: 🟡 Medium
Topics: String, Stack, Recursion

Solution

LeetCode 394 - Decode String

Problem Understanding

The problem gives us a string that contains encoded patterns of the form k[encoded_string]. The integer k tells us how many times the substring inside the brackets should be repeated. Our task is to fully decode the string and return the expanded result.

For example, the input:

3[a]

means the string "a" should be repeated 3 times, producing:

aaa

The problem becomes more interesting because the encoded substrings can be nested. Consider:

3[a2[c]]

The inner pattern 2[c] becomes "cc", so the outer pattern becomes:

3[acc]

which finally expands to:

accaccacc

The input string consists only of lowercase letters, digits, and square brackets. The problem guarantees that the input is always valid. This means:

• Every opening bracket has a matching closing bracket
• Numbers always appear before brackets
• Digits are only used for repetition counts
• There are no malformed patterns

The maximum input length is only 30 characters, but the decoded output can grow much larger, up to 10^5 characters. This tells us that even though the encoded string is short, we must carefully build the decoded result efficiently.

Several edge cases are important:

• Nested encodings such as "2[a3[b]]"
• Multi-digit repetition counts such as "12[a]"
• Strings that contain normal characters outside encoded sections such as "abc3[cd]xyz"
• Deep nesting levels
• Single-character inputs without brackets

A naive parser can easily fail when handling nested structures or multi-digit numbers, so we need a structured approach.

Approaches

Brute Force Approach

A brute force solution repeatedly searches for the innermost bracket pair, decodes it, replaces it in the string, and continues until no brackets remain.

For example:

3[a2[c]]

would first locate:

2[c]

replace it with:

cc

resulting in:

3[acc]

Then it would decode again to produce:

accaccacc

This approach works because decoding the innermost expression first guarantees that nested expressions are resolved in the correct order.

However, repeatedly scanning and rebuilding strings is inefficient. Every replacement may require copying large portions of the string. With deeply nested or heavily repeated inputs, this becomes expensive.

Optimal Approach, Stack-Based Parsing

The key observation is that decoding naturally follows a nested structure, which makes a stack an ideal data structure.

Whenever we encounter a new bracketed expression:

• We save the current partially built string
• We save the repetition count
• We begin building the inner substring

When we reach a closing bracket:

• We complete the current substring
• Repeat it the required number of times
• Append it back to the previous string context

This mirrors how nested expressions work mathematically.

A stack allows us to efficiently pause and resume previous decoding contexts without repeatedly rescanning the string.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) or worse	O(n)	Repeated rescanning and string rebuilding
Optimal	O(n + output)	O(n + output)	Single pass using stacks

Algorithm Walkthrough

Step 1: Initialize Data Structures

We maintain:

• A stack for repetition counts
• A stack for previously built strings
• A variable for the current number being parsed
• A variable for the current decoded substring

The stacks help us return to previous contexts after finishing nested expressions.

Step 2: Traverse the String Character by Character

We iterate through every character in the input string.

Each character belongs to one of four categories:

• Digit
• Opening bracket [
• Closing bracket ]
• Alphabet character

Step 3: Handle Digits

If the character is a digit, we update the current number.

This is important because repetition counts may contain multiple digits.

For example:

12[a]

must be parsed as 12, not 1 and 2.

We compute:

current_number = current_number * 10 + digit

Step 4: Handle Opening Brackets

When we encounter [, it means a new nested substring begins.

At this point:

1. Push the current repeat count onto the count stack
2. Push the current built string onto the string stack
3. Reset the current string
4. Reset the current number

This effectively starts a fresh decoding context for the inner substring.

Step 5: Handle Alphabet Characters

If the character is a normal letter, append it to the current substring.

Example:

current_string += char

Step 6: Handle Closing Brackets

When we encounter ], the current substring is complete.

We then:

1. Pop the repetition count
2. Pop the previous string context
3. Repeat the current substring
4. Append the repeated result to the previous string

This reconstructs the decoded string layer by layer.

Step 7: Return the Final String

After processing the entire input, the current string contains the fully decoded result.

Why It Works

The algorithm maintains a correct decoding context at every nesting level. Whenever a new bracket begins, the current state is saved. Whenever a bracket ends, the inner decoded substring is combined with its parent context. Since brackets are processed in properly nested order, the stack always restores the correct previous state. This guarantees that nested expressions are decoded correctly.

Python Solution

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

        current_num = 0
        current_string = ""

        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)

            elif char == "[":
                count_stack.append(current_num)
                string_stack.append(current_string)

                current_num = 0
                current_string = ""

            elif char == "]":
                repeat_count = count_stack.pop()
                previous_string = string_stack.pop()

                current_string = previous_string + current_string * repeat_count

            else:
                current_string += char

        return current_string

The implementation follows the algorithm directly.

The count_stack stores repetition counts for nested expressions. The string_stack stores the string built before entering a nested section.

The variable current_num accumulates digits to correctly handle multi-digit repetition counts. The variable current_string stores the substring currently being decoded.

When an opening bracket appears, the current state is pushed onto the stacks because we are entering a deeper nesting level. The current variables are then reset to begin decoding the inner substring independently.

When a closing bracket appears, we pop the saved repetition count and previous string. The current substring is repeated and appended to the previous context.

Since the traversal happens in a single pass, the algorithm efficiently handles nested structures without rescanning the string.

Go Solution

func decodeString(s string) string {
	countStack := []int{}
	stringStack := []string{}

	currentNum := 0
	currentString := ""

	for _, char := range s {
		if char >= '0' && char <= '9' {
			currentNum = currentNum*10 + int(char-'0')

		} else if char == '[' {
			countStack = append(countStack, currentNum)
			stringStack = append(stringStack, currentString)

			currentNum = 0
			currentString = ""

		} else if char == ']' {
			repeatCount := countStack[len(countStack)-1]
			countStack = countStack[:len(countStack)-1]

			previousString := stringStack[len(stringStack)-1]
			stringStack = stringStack[:len(stringStack)-1]

			repeated := ""
			for i := 0; i < repeatCount; i++ {
				repeated += currentString
			}

			currentString = previousString + repeated

		} else {
			currentString += string(char)
		}
	}

	return currentString
}

The Go implementation follows the same logic as the Python version, but uses slices as stacks.

Go strings are immutable, so repeated concatenation creates new strings. This is acceptable within the problem constraints, though in larger-scale scenarios a strings.Builder could improve efficiency.

Stack popping is implemented by slicing:

stack = stack[:len(stack)-1]

Unlike Python, Go requires explicit rune-to-string conversion when appending characters.

Worked Examples

Example 1

Input:

3[a]2[bc]

Step-by-Step Trace

Character	Action	Current Num	Current String	Count Stack	String Stack
3	Build number	3	""	[]	[]
[	Push state	0	""	[3]	[""]
a	Append char	0	"a"	[3]	[""]
]	Decode section	0	"aaa"	[]	[]
2	Build number	2	"aaa"	[]	[]
[	Push state	0	""	[2]	["aaa"]
b	Append char	0	"b"	[2]	["aaa"]
c	Append char	0	"bc"	[2]	["aaa"]
]	Decode section	0	"aaabcbc"	[]	[]

Final result:

aaabcbc

Example 2

Input:

3[a2[c]]

Step-by-Step Trace

Character	Action	Current Num	Current String	Count Stack	String Stack
3	Build number	3	""	[]	[]
[	Push state	0	""	[3]	[""]
a	Append char	0	"a"	[3]	[""]
2	Build number	2	"a"	[3]	[""]
[	Push state	0	""	[3,2]	["","a"]
c	Append char	0	"c"	[3,2]	["","a"]
]	Decode inner	0	"acc"	[3]	[""]
]	Decode outer	0	"accaccacc"	[]	[]

Final result:

accaccacc

Example 3

Input:

2[abc]3[cd]ef

Step-by-Step Trace

Character	Action	Current Num	Current String
2	Build number	2	""
[	Push state	0	""
a	Append	0	"a"
b	Append	0	"ab"
c	Append	0	"abc"
]	Decode	0	"abcabc"
3	Build number	3	"abcabc"
[	Push state	0	""
c	Append	0	"c"
d	Append	0	"cd"
]	Decode	0	"abcabccdcdcd"
e	Append	0	"abcabccdcdcde"
f	Append	0	"abcabccdcdcdef"

Final result:

abcabccdcdcdef

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + output)	Each character is processed once, plus construction of the decoded output
Space	O(n + output)	Stacks and final decoded string require additional memory

The algorithm performs a single left-to-right traversal of the encoded string. Every character is processed once, and every decoded character is written once into the final result.

The stack size depends on the nesting depth, which is at most proportional to the input size. The output string itself may contain up to 10^5 characters, which dominates the space usage.

Test Cases

solution = Solution()

assert solution.decodeString("3[a]2[bc]") == "aaabcbc"  # basic multiple groups
assert solution.decodeString("3[a2[c]]") == "accaccacc"  # nested encoding
assert solution.decodeString("2[abc]3[cd]ef") == "abcabccdcdcdef"  # trailing characters

assert solution.decodeString("1[a]") == "a"  # minimum repeat
assert solution.decodeString("10[a]") == "aaaaaaaaaa"  # multi-digit number

assert solution.decodeString("2[a3[b]]") == "abbbabbb"  # nested structure
assert solution.decodeString("3[z2[y]]") == "zyyzyyzyy"  # nested repeated groups

assert solution.decodeString("abc") == "abc"  # no encoding
assert solution.decodeString("xyz2[a]") == "xyzaa"  # prefix characters
assert solution.decodeString("2[a]xyz") == "aaxyz"  # suffix characters

assert solution.decodeString("2[3[a]b]") == "aaabaaab"  # mixed nesting
assert solution.decodeString("12[x]") == "xxxxxxxxxxxx"  # larger repetition count

assert solution.decodeString("2[ab3[c]]") == "abcccabccc"  # nested repetition inside text

Test Summary

Test	Why
"3[a]2[bc]"	Basic decoding functionality
"3[a2[c]]"	Validates nested decoding
"2[abc]3[cd]ef"	Checks plain text outside brackets
"1[a]"	Smallest valid repetition
"10[a]"	Multi-digit repeat count
"2[a3[b]]"	Nested repetition handling
"3[z2[y]]"	Multiple nested layers
"abc"	Input without brackets
"xyz2[a]"	Prefix before encoded section
"2[a]xyz"	Suffix after encoded section
"2[3[a]b]"	Combination of nested and plain text
"12[x]"	Larger repetition counts
"2[ab3[c]]"	Nested repeated suffix

Edge Cases

Multi-Digit Repeat Counts

An input like:

12[a]

can cause bugs if digits are processed independently. A naive implementation might interpret this as 1 followed by 2.

The solution correctly accumulates digits using:

current_num = current_num * 10 + int(char)

This ensures all digits are combined into the correct integer value.

Deeply Nested Encodings

Inputs such as:

2[a3[b2[c]]]

contain several nested levels. Recursive or poorly managed implementations can lose track of which substring belongs to which repetition count.

The stack-based approach solves this cleanly by saving each decoding context independently. Every opening bracket creates a new level, and every closing bracket restores the previous level correctly.

Plain Characters Outside Encoded Sections

Inputs like:

abc3[cd]xyz

contain normal characters before and after encoded patterns.

A buggy implementation may accidentally overwrite earlier text when decoding a bracketed section. This solution preserves previous content by storing the earlier string on the stack and appending the decoded substring back to it after processing the brackets.