Decoded String at Index LeetCode 880

LeetCode 880 — Decoded String at Index — gives you an encoded string s consisting of lowercase letters and digits 2-9. A digit d means the entire decoded string so far is repeated d times. Given an integer k, return the k-th letter (1-indexed) in the decoded string.

For example, s = "leet2code3" decodes to "leetleetcodeleetleetcodeleetleetcode". The decoded string can be astronomically long — up to 2^63 characters — so building it is impossible. You must find the k-th character without constructing the string.

The key insight is to work backwards. First compute the total decoded length in a forward pass. Then scan backwards: when you hit a digit, the length shrinks (divide by the digit) and k wraps around (k %= length). When you hit a letter and k equals 0 or matches the current position, that is the answer.

Scan s from left to right, maintaining a variable size representing the current decoded string length. When you encounter a letter, increment size by 1. When you encounter a digit d, multiply size by d. Stop when size >= k (we have enough information).

This forward pass is straightforward but critical. It tells us the total length of the decoded string at each position in s. We need this information for the backward pass because the digit multiplications define how the string folds onto itself.

Use a 64-bit integer (long in Java, int in Python which has arbitrary precision) for size. The decoded length can exceed 2^63, but we only need to track it until it exceeds k, which is at most 10^9. In practice, a few multiplications by large digits quickly surpass k.

Scan s from right to left (starting from where the forward pass stopped). At each position, check whether the character is a digit or a letter. The logic differs for each case, and together they unwind the encoding to pinpoint the k-th character.

If the character is a digit d: the string at this point is a d-fold repetition of the preceding string. Divide size by d to get the length of one copy. Then take k %= size — this maps k into the equivalent position within one copy. If k becomes 0, it maps to the last character of the copy.

If the character is a letter: this letter occupies position size in the decoded string. If k equals 0 or k equals size, this is the answer — return it. Otherwise, decrement size by 1 (this letter added 1 to the length) and continue backward.

Consider s = "ha22", k = 5. Forward pass: h→size=1, a→size=2, 2→size=4, 2→size=8. size=8 >= k=5, stop. Decoded string is "hahahaha" (8 chars). We want the 5th character.

Backward pass: i=3, char "2", size=8/2=4, k=5%4=1. i=2, char "2", size=4/2=2, k=1%2=1. i=1, char "a", size=2, k=1 != 0 and k!=2, size=2-1=1. i=0, char "h", size=1, k=1 == size=1, return "h".

Verify: "hahahaha"[5] (1-indexed) = "h". Correct! The modular arithmetic unwound the two doublings to trace position 5 back to position 1 in the base string "ha", which is "h".

In Python, the forward pass uses a simple loop: for c in s, if c.isdigit() then size *= int(c), else size += 1. Stop when size >= k. The backward pass iterates range(len(s)-1, -1, -1) applying the digit/letter logic.

In Java, use a long for size to handle large intermediate values. The forward loop is identical. The backward loop uses Character.isDigit() to distinguish cases. Return String.valueOf(s.charAt(i)) when the answer is found.

A common implementation mistake is not handling k=0 correctly in the backward pass. After k %= size, if k becomes 0 and the current character is a letter, that is the answer. Missing this check causes the loop to continue past the correct position.

Time complexity is O(n) where n is the length of the encoded string s. The forward pass scans s once. The backward pass scans s once in reverse. Each character is processed at most twice.

Space complexity is O(1). We use only a constant number of variables: size, k, and the loop index. No auxiliary arrays or strings are needed. This is remarkable given that the decoded string can be exponentially long.

This is optimal — we must read each character of s at least once to understand the encoding. The O(1) space is the key achievement: we find a specific character in a potentially 2^63-character string using constant memory.

Decode String (LeetCode 394) uses a stack to handle nested brackets like "3[a2[c]]". While the encoding format differs, both problems require understanding how repetition affects string positions. Decode String builds the string; Decoded String at Index avoids building it.

String Compression (LeetCode 443) and Count and Say (LeetCode 38) are other encoding/decoding problems that test string manipulation skills. They focus on forward processing rather than the reverse simulation used here.

Kth Symbol in Grammar (LeetCode 779) is another problem where you find the k-th element in a recursively defined sequence without building it. The same reverse-tracing technique applies: work backwards, reducing the problem at each step until you reach the base case.