Decoded String at Index: Reverse Traversal Without Building the String

You are given an encoded string s made of lowercase letters and digits 2 through 9. When you encounter a letter, it appends to the tape. When you encounter a digit d, the entire tape so far is repeated d times. Given an integer k, return the k-th letter (1-indexed) in the decoded string.

This is LeetCode 880: Decoded String at Index, and it tests whether you can avoid the brute-force trap. The decoded string can be astronomically long (up to 2^63 characters), so building it is not an option. Instead, you work backwards from the total size to pinpoint exactly which character sits at position k.

Why this problem matters

Decoded String at Index teaches a powerful general technique: when the forward process creates something too large to store, reverse the process and narrow down incrementally. You will see this same "work backwards" idea in problems involving modular arithmetic, index mapping, and any scenario where the output space explodes exponentially but the answer is a single element.

It also reinforces the distinction between "what the problem describes" and "what you actually need to compute." The problem describes building a giant string. What you actually need is one character. That gap between the description and the real task is where the insight lives.

The approach: reverse traversal

The key observation is that digits multiply the string length, and letters add one to it. You can compute the total decoded length in a single forward pass without building anything. Once you know the total size, walk backwards through the encoded string:

• If you hit a digit d, the string of length size was created by repeating a shorter string of length size / d. Set size = size / d and k = k % size. If k becomes 0, it means the target is the last character of the shorter string (equivalent to position size).
• If you hit a letter, this character sits at position size. If k == size or k % size == 0, you found your answer. Otherwise, decrement size by 1 and keep going.

This works because each digit "folds" the string back onto itself. The modulo operation finds where k would land in the shorter version.

The solution

def decodeAtIndex(s, k):
    size = 0
    for ch in s:
        if ch.isdigit():
            size *= int(ch)
        else:
            size += 1

    for i in range(len(s) - 1, -1, -1):
        k %= size
        if k == 0 and s[i].isalpha():
            return s[i]
        if s[i].isdigit():
            size //= int(s[i])
        else:
            size -= 1

    return ""

Visual walkthrough

Let's trace through s = "leet2code3" with k = 10. First we compute the total decoded size, then walk backwards to find the answer.

The reverse pass processed only 4 characters before finding the answer. No matter how large the decoded string would be, the reverse traversal always finishes in at most len(s) steps.

Complexity analysis

The forward pass computes the total size in O(n). The backward pass walks through the string at most once. No auxiliary data structures are needed beyond a couple of integer variables. This is optimal since you must read every character at least once.

Building blocks

This problem is built on two key ideas:

Reverse index mapping. Instead of building the decoded string and looking up index k, you reverse-engineer which original character maps to that index. The same "trace backwards" strategy appears whenever a transformation is invertible. For example, in problems involving repeated permutations or cyclic rotations, you can often undo steps to find where an element came from without simulating the entire process.

Modular arithmetic for position folding. When a digit d repeats the string, position k in the long string maps to position k % size in the short string. This modulo-based folding is the same idea behind circular array indexing and problems like Josephus problem. Recognizing that repetition plus modulo lets you "collapse" an exponentially large space into a small one is a skill that transfers across many problems.

Edge cases to watch for

• k lands exactly on a boundary: when k % size == 0 after a digit reduction, the answer is the last letter of the shorter string, not the first. You need to keep walking backwards until you find an actual letter at that position.
• Single letter then digit: "a23" with k = 1. The decoded string is "aaaaaa". Every position is "a". The modulo collapses k to 0, and you return the letter.
• k equals total size: k equals the full decoded length. After the first modulo step, k becomes 0. You need to find the last letter that contributed to the string.
• Leading letters with no digits: "abc" with k = 2. No digits at all. The backward walk simply decrements size until it matches k, returning "b".
• Large digit multipliers: "a2345678999999999" can produce decoded lengths near 2^63. Your size variable must handle large integers (Python does this natively, but in other languages use 64-bit integers).

From understanding to recall

You now understand why building the decoded string is impossible and how reverse traversal avoids it. The two core moves are: (1) compute total size forward, (2) walk backward with modulo to shrink k until it points to a letter.

The part that trips people up in interviews is the k == 0 check. When k % size gives 0, it means the target is the last character of the current substring, not the first. You need to keep scanning backwards until you hit an actual letter at that position. Missing this case causes off-by-one bugs that are hard to debug under time pressure.

Spaced repetition helps lock in the two-pass structure, the modulo logic, and the k == 0 edge case. After a few repetitions, writing this solution from scratch takes under five minutes and the tricky boundary conditions become automatic.

Related posts

• Decode String - Stack-based string expansion with nested brackets, a related encoding/decoding problem
• Decode Ways - Dynamic programming approach to counting valid decodings of a digit string
• String Compression - In-place string manipulation using read/write pointers