Abstract / Summary

Given a string with encoded sequences of repeated characters return the fully expanded string according to the encoding rules

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 63% (2+ million submissions).

Typical patterns to solve this problem:

• Recursion
• Stack
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation decodes an encoded string that follows the pattern k[encoded_string] where k is a positive integer indicating how many times encoded_string should be repeated. The algorithm processes the input in a single left-to-right pass, using a stack to keep track of pending repetitions and the partially built result for each nesting level. The final decoded string is returned after the loop finishes.

Initialization

At the start, three variables are prepared:

todo = []
num  = ""
text = ""

• todo acts as a stack that stores tuples of the form (repeat count, outer text) for each opened bracket.
• num accumulates consecutive digit characters to form the repeat count.
• text holds the characters that belong to the current nesting level.

Main Loop

The core of the algorithm iterates over each character c in the input string s:

for c in s:
    ...

Inside the loop four distinct cases are distinguished.

Encountering an Opening Bracket

When c is '[', the current number and text are pushed onto the stack, and the accumulators are reset for the new inner segment:

if c == "[":
    todo.append((int(num), text))
    num  = ""
    text = ""

This step captures the repeat count (int(num)) and the string built so far (text) before descending into a deeper level.

Encountering a Closing Bracket

When c is ']', the most recent context is popped from the stack, the inner text is repeated, and then concatenated with the outer text that was saved earlier:

elif c == "]":
    repeat, outer = todo.pop()
    text = outer + text * repeat

The multiplication text * repeat expands the inner segment, and the result is attached to the outer segment, effectively collapsing one level of nesting.

Processing Digits

If the character is a digit, it is appended to num to allow multi-digit repeat counts:

elif c.isdigit():
    num += c

By building the number as a string and converting it only when an opening bracket is seen, the code avoids repeated integer parsing.

Processing Alphabetic Characters

Any character that is not a bracket or a digit is treated as a literal part of the current segment and appended to text:

else:
    text += c

This includes lower-case letters, upper-case letters, and any other non-digit, non-bracket symbols that may appear in the encoded string.

Final Result

After the loop completes, text contains the fully decoded string, which is returned directly:

return text

If the input string contains no brackets, the loop never pushes or pops from the stack, and text simply accumulates the original characters, resulting in an identity transformation.

Edge Cases Handled

The algorithm gracefully manages several edge conditions:

• Nested encodings such as "3[a2[b]]" are decoded correctly because each '[' pushes a new context and each ']' pops and resolves the most recent one, preserving the proper order of expansion.
• Multi-digit repeat counts like "12[ab]" are supported because digits are concatenated into num until the opening bracket signals conversion to an integer.
• Empty inner sections (e.g., "2[]") produce an empty string for that segment, and the outer concatenation still respects the repeat count, yielding an empty contribution.
• Strings without any brackets (e.g., "hello") bypass the stack logic entirely, returning the original string unchanged.
• Consecutive literals after a closing bracket (e.g., "2[ab]c") are appended to text after the inner segment is resolved, ensuring correct ordering.

Performance Optimizations Observed

• Single pass processing eliminates the need for multiple scans or recursive calls, keeping the runtime proportional to the length of the input.
• Stack reuse via a Python list (todo) provides O(1) push and pop operations, which is efficient for deep nesting.
• Deferred integer conversion occurs only when an opening bracket is encountered, reducing the number of int() calls compared with converting each digit individually.
• Local variable usage (num, text, repeat, outer) minimizes attribute lookups and speeds up the loop body.
• String multiplication (text * repeat) leverages Python’s optimized C implementation for repeating sequences, avoiding manual concatenation loops.

These choices collectively ensure that the function runs quickly even for long strings with many nested repetitions.

Imagine a magical box that knows how to follow secret instructions written in a special code. Sometimes the instruction says to write a word, but other times it says to repeat a word many times.

The computer starts with an empty notebook called todo and two empty slates called num and text. It looks at every symbol in the string one by one.

When the computer sees a number, it writes that digit on the num slate so it remembers how many times to do the trick later.

When it sees an opening bracket, it knows a secret message is about to start. It takes the number it found and puts it into the notebook along with any words it has gathered so far. After that, it cleans the slates so they are ready for the new part of the message.

When it sees a normal letter like a or b, it puts that letter onto the text slate.

When it sees a closing bracket, the magic happens. It takes the last number and the old words out of the notebook. It takes the words it just finished building and repeats them as many times as the number says. Then it sticks that long string onto the end of the old words it saved earlier.

The computer does this over and over until it has finished reading every single part of the instructions. By the end, all the pieces are put together into one long, finished sentence.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python			TS
	WalkCCC	C++	Java	Python
	leetcode.ca		Java	Python			TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	AdelDaniel												Dart
	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis					JS
	fartem									Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan		Java
	halfrost											Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	luangong						TS
	MacJim	C++
	martianoff							Scala
	ruoru								Rust
	suxrobGM				C#
	trung-hn			Python
	varunu28		Java
	vli02													C
	vthwang		Java
	XiaotaoGuo	C++
	yuanliu666										Kotlin
	YuriSpiridonov			Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
AdelDaniel	Dart
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
luangong	TypeScript
MacJim	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality