Decoded String at Index - Video Solutions

Problem Overview: The string s contains letters and digits. Letters append directly to a decoded string, while digits repeat the entire current decoded sequence d-1 more times. The decoded string can become extremely large, so you cannot build it directly. The task is to return the kth character of the final decoded string.

Approach 1: Iterative Length Expansion Simulation (O(n) time, O(1) space)

Scan the string from left to right and track the length of the decoded string without actually constructing it. When you encounter a letter, increment the length. When you encounter a digit d, multiply the current length by d because the entire sequence repeats. Once the computed length reaches or exceeds k, you know the answer lies within the prefix processed so far. This approach models the decoding process mathematically using string traversal rather than allocating memory for the decoded string.

Approach 2: Decode Length Backtracking (O(n) time, O(1) space)

This is the most common optimal solution. First pass: compute the total decoded length using the same expansion logic. Second pass: traverse the string backward and reduce k relative to the current decoded length. When you hit a digit, divide the length by that digit because you are stepping back through the repeated blocks. When you hit a letter, check if k == 0 or k == length. If true, that character is the answer. The key insight is that the decoded string forms repeating segments, so modulo arithmetic lets you map k back into earlier segments.

Approach 3: Reverse Decoding Simulation (O(n) time, O(1) space)

This variation also processes the string backward but focuses on simulating how the index shrinks as repetition layers are removed. Each digit compresses the decoded length by dividing it, while letters decrement the length by one. If the adjusted index matches the current position, you return that character. This technique avoids recursion and keeps only a few integer variables, making it efficient for very large decoded lengths.

Approach 4: Iterative Length Calculation with Stack Insight (O(n) time, O(1) space)

Although no explicit stack is required, the algorithm behaves like unwinding nested expansions. Each digit acts like pushing a repetition frame, and the reverse traversal pops those frames while shrinking the search index. Understanding this structure helps when reasoning about nested repetitions and aligns conceptually with problems involving stack-like backtracking over encoded sequences.

Recommended for interviews: The Decode Length Backtracking approach is what interviewers expect. It demonstrates that you recognize the decoded string may exceed memory limits and that you can reason about the structure mathematically. Explaining why constructing the string is infeasible shows good problem analysis, while the backward traversal with modulo arithmetic proves strong algorithmic thinking with string processing.