You are given an encoded string s. To decode the string to a tape, the encoded string is read one character at a time and the following steps are taken:
d, the entire current tape is repeatedly written d - 1 more times in total.Given an integer k, return the kth letter (1-indexed) in the decoded string.
Example 1:
Input: s = "leet2code3", k = 10 Output: "o" Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10th letter in the string is "o".
Example 2:
Input: s = "ha22", k = 5 Output: "h" Explanation: The decoded string is "hahahaha". The 5th letter is "h".
Example 3:
Input: s = "a2345678999999999999999", k = 1 Output: "a" Explanation: The decoded string is "a" repeated 8301530446056247680 times. The 1st letter is "a".
Constraints:
2 <= s.length <= 100s consists of lowercase English letters and digits 2 through 9.s starts with a letter.1 <= k <= 109k is less than or equal to the length of the decoded string.263 letters.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.
This approach involves simulating the decoding process in reverse. Instead of constructing the entire decoded string, we keep track of its potential length. The core idea is to process the string in reverse while maintaining the effective length given the repeat operations.
When a digit is encountered, it denotes how many times the current segment should be repeated to match the original decoding logic. Conversely, letters are treated based on their position in this accumulated length.
By working backwards, when the kth character location matches a letter’s position, it indicates we navigated back through the expansions accurately to find the original letter corresponding to the kth position.
The Python implementation computes the length of the decoded string indirectly by iterating over the encoded characters. When digits are encountered, they scale the accumulated size. By reverting the transformations in the reverse iteration, the character’s position (k) is resolved modulo size to back-calculate its source during the construction. If k mod size becomes zero next to a letter, it confirms the correct backward mapping of the kth position corresponds to that letter.
Python
Time Complexity: O(n), where n is the length of the string s, as it requires scanning through the string and possibly rescanning for finding the exact letter.
Space Complexity: O(1), no extra space is used apart from constants.
This alternative approach iteratively simulates the expansion of the tape until the kth position is intelligibly reached. We avoid producing the content itself but calculate how long the tape would be if fully decoded. Upon encountering the kth target, we can infer shortly by aligning tape lengths with character identities. Essentially, this approach is an iterative construct of the maximal state, allowing us to peel back layers in a controlled manner.
In this JavaScript solution, we iteratively scan to expand the tape size as dictated by the input string. Each character’s impact on the tape accumulating length is considered until the target k value can be mapped definitively backward. The deviation to discover a letter when it resolves directly to size multiples (mod k condition) signals those fit criteria.
JavaScript
Time Complexity: O(n), iterates over the encoded string twice.
Space Complexity: O(1), uses constant extra space.
This approach involves calculating the length of the decoded string dynamically and using that information to find the k-th character by backtracking. Instead of generating the complete decoded string, we track the total effective length as we simulate the decoding process.
The function decodeAtIndex calculates the size of the theoretical decoded string without actually creating it. It iterates through the string, calculating this size. As you move backwards, update k using k %= size. If you find a letter where k becomes zero, you’ve found the k-th character.
Time Complexity: O(n), where n is the length of the string, as we iterate through it twice.
Space Complexity: O(1), as only a fixed amount of space is used.
This approach is quite similar to the backtracking approach, but emphasizes deeper understanding by dissecting the string iteratively and understanding the effective final character through targeted calculation at each stage of string development without evaluating unneeded sections.
This variation emphasizes understanding through excitement in code stepping for size calculation and extraction of the effective character to showcase order of operation purpose more through breakdown as encountered at each string interaction.
Time Complexity: O(n). Every character in the string is utilized only once in theory analysis.
Space Complexity: O(1).
We can first calculate the total length m of the decoded string, then traverse the string from back to front. Each time, we update k to be k bmod m, until k is 0 and the current character is a letter, then we return the current character. Otherwise, if the current character is a number, we divide m by this number. If the current character is a letter, we subtract 1 from m.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Reverse Decoding Simulation | Time Complexity: O(n), where n is the length of the string s, as it requires scanning through the string and possibly rescanning for finding the exact letter. |
| Iterative Length Expansion Simulation | Time Complexity: O(n), iterates over the encoded string twice. |
| Decode Length Backtracking | Time Complexity: O(n), where n is the length of the string, as we iterate through it twice. |
| Iterative Length Calculation | Time Complexity: O(n). Every character in the string is utilized only once in theory analysis. |
| Reverse Thinking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Length Expansion Simulation | O(n) | O(1) | When you want to model decoded length without building the string |
| Decode Length Backtracking | O(n) | O(1) | Best general solution and most expected in interviews |
| Reverse Decoding Simulation | O(n) | O(1) | When implementing a clean backward traversal without extra structures |
| Iterative Length Calculation | O(n) | O(1) | When reasoning about nested repetitions similar to stack unwinding |
Decoded String at Index | Clean Code | TCS | GOOGLE | ORACLE | Leetcode - 880 • codestorywithMIK • 17,115 views views
Watch 9 more video solutions →Practice Decoded String at Index with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor