Abstract / Summary

Given an encoded string and an index return the character at that position after fully decoding the string without actually decoding it.

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 37% (200k+ submissions).

Typical patterns to solve this problem:

• 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 defines a Solution class with a method decodeAtIndex that determines the character located at a 1-based position k in a decoded string generated from an encoded pattern s. The encoding consists of lowercase letters and digits; each digit indicates that the current built string should be repeated that many times. The algorithm avoids constructing the full decoded string, which could be prohibitively large, by working backwards through a stack representation of the encoded input.

Construction of the processing stack

The first logical block transforms the input string into a list named todo. Each character is examined; digits are converted to integers while letters are kept as strings. This conversion creates a uniform structure where each element’s type signals whether it contributes a single character or a multiplicative factor.

todo = []
for c in s:
    todo.append(int(c) if c.isdigit() else c)

By storing the elements in order, the algorithm can later pop from the end to simulate reverse traversal of the encoded sequence.

Length calculation helper

A nested function length computes the total length of the decoded string represented by the current state of todo. It iterates over the list, adding one for each character and multiplying the accumulated length by each digit encountered. The result reflects the size of the fully expanded string at that point.

def length():
    result = 0
    for t in todo:
        if type(t) == str:
            result += 1
        else:
            result *= t
    return result

Because length is invoked repeatedly inside the main loop, its design as a compact linear scan contributes to the overall efficiency of the method.

Main reverse-iteration loop

The core of the algorithm is a loop that runs exactly as many times as there are elements in todo. At each iteration the current target index k is reduced modulo the current decoded length, effectively mapping k into the range of the current representation. This modulo operation handles the wrap-around behavior when the decoded string repeats.

for _ in range(len(todo)):
    k %= length()

After adjusting k, the algorithm removes the last element from todo. If the removed element is a character, a direct comparison determines whether k has reached zero; when it does, that character is the answer and is returned immediately.

last = todo.pop()
if type(last) == str:
    if k == 0:
        return last

When the popped element is a digit, the algorithm implicitly continues the loop, allowing the next iteration to work with the shortened stack. The modulo reduction performed earlier ensures that the index correctly reflects the position within the repeated segment before the digit’s expansion.

Edge-case handling

The method gracefully handles several edge conditions without explicit branching. When k equals the total length of the decoded string, the modulo operation yields zero, positioning the search at the final character of the current representation. This case is correctly resolved by the if k == 0 check after popping a character.

If the encoded string begins with a digit, the initial length calculation treats the digit as a multiplier of an empty prefix, resulting in a length of zero; however, the problem constraints guarantee that the first character is a letter, so the algorithm operates under that implicit precondition.

When the encoded pattern contains consecutive digits, each digit is treated as a separate multiplier applied sequentially, and the length function multiplies accordingly. The reverse iteration naturally collapses these nested repetitions, and the modulo reduction continues to map k into the appropriate sub-segment.

If k is larger than the total decoded length, the initial modulo operation reduces it to a valid position within the range, ensuring that the algorithm never attempts to access an out-of-bounds index.

Performance optimizations

The primary optimization lies in avoiding full materialization of the decoded string. By representing the encoded input as a stack of atomic operations and computing lengths on demand, the algorithm reduces memory consumption dramatically, regardless of how many times the string repeats.

The use of a modulo operation at the start of each iteration compresses the search space, effectively “rewinding” the index through repeated sections without iterating through each character of the expanded string. This approach transforms what could be an exponential expansion into a linear pass over the original encoded characters.

Storing digits as integers rather than strings eliminates repeated parsing during length calculations, allowing the multiplication step to be performed directly. The type check type(t) == str distinguishes between characters and multipliers with minimal overhead.

Finally, the loop iterates exactly the number of elements originally present in todo. Because each iteration removes one element, the total number of iterations is bounded by the length of the input string, guaranteeing a predictable execution path that scales with the size of the encoded representation rather than the size of its decoded form.

Imagine a long train made of building blocks. Some blocks are letters and some are special multipliers that make the train grow by repeating what came before. The code first looks at all the blocks and lines them up in a row. It calculates the total size of the train if the multipliers were used to expand it.

To find a specific block at a secret position, the code starts from the back of the train and works its way to the front. It uses the magic of math to shrink the target position down so that it fits within the current size of the train. Every time it hits a multiplier, it shrinks the target down even further. If it finds a letter block when the target position reaches zero, that letter is the secret one being looked for.

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++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java				Go		TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fartem						Ruby
	fsq	C++
	gouthampradhan			Java
	halfrost							Go
	JoshCrozier				JS
	lkwq007		Python
	MacJim	C++
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	varunu28			Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

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