Skip to main content
Talentd

Decoded String at Index - Solution & Explanation

MediumStringStack19 min readAsked at: Amazon, Meta, PhonePe +2
Practice this problem

Problem Statement

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:

  • If the character read is a letter, that letter is written onto the tape.
  • If the character read is a digit 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 <= 100
  • s consists of lowercase English letters and digits 2 through 9.
  • s starts with a letter.
  • 1 <= k <= 109
  • It is guaranteed that k is less than or equal to the length of the decoded string.
  • The decoded string is guaranteed to have less than 263 letters.

Approach Overview

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.

Approach 1: Reverse Decoding Simulation

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Length Expansion Simulation

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.

Code

JavaScript

JavaScript

Complexity

Time Complexity: O(n), iterates over the encoded string twice.
Space Complexity: O(1), uses constant extra space.

Try this approach in the editor →

Approach 3: Decode Length Backtracking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 4: Iterative Length Calculation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n). Every character in the string is utilized only once in theory analysis.
Space Complexity: O(1).

Try this approach in the editor →

Approach 5: Reverse Thinking

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), no extra space is used apart from constants.

Iterative Length Expansion Simulation

Time Complexity: O(n), iterates over the encoded string twice.
Space Complexity: O(1), uses constant extra space.

Decode Length Backtracking

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.

Iterative Length Calculation

Time Complexity: O(n). Every character in the string is utilized only once in theory analysis.
Space Complexity: O(1).

Reverse Thinking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Length Expansion SimulationO(n)O(1)When you want to model decoded length without building the string
Decode Length BacktrackingO(n)O(1)Best general solution and most expected in interviews
Reverse Decoding SimulationO(n)O(1)When implementing a clean backward traversal without extra structures
Iterative Length CalculationO(n)O(1)When reasoning about nested repetitions similar to stack unwinding

Video Solution

Decoded String at Index | Clean Code | TCS | GOOGLE | ORACLE | Leetcode - 880 • codestorywithMIK • 19,021 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Decoded String at Index easy or hard?
Decoded String at Index is rated Medium on LeetCode but feels closer to Medium-Hard for many candidates. The challenge is recognizing that the decoded string can be astronomically large and that the solution requires mathematical backtracking rather than direct construction.
Decoded String at Index Python/Java solution
Python, Java, C++, and JavaScript solutions typically implement the same two-phase approach: compute decoded length, then traverse backward adjusting k. Python solutions often rely on Python's large integer support, while Java and C++ implementations use long variables to store the decoded length.
How to solve Decoded String at Index in O(n)?
Compute the total decoded length by iterating through the string and multiplying the length whenever a digit appears. Then traverse the string backward, updating k using k %= length and shrinking the length when encountering digits. When a letter satisfies k == 0 or k == length, that character is the answer.
What is the best approach for Decoded String at Index?
The decode length backtracking approach is considered the optimal solution. It first computes the decoded length while scanning the string, then walks backward adjusting k using modulo operations. This avoids building the massive decoded string and runs in O(n) time with O(1) extra space.
Is Decoded String at Index asked at Google/Amazon/Meta?
Decoded String at Index has appeared in interviews at large tech companies including Google and Amazon because it tests reasoning about exponential growth in strings. Candidates must avoid brute force decoding and instead apply mathematical simulation and backward traversal.
What data structure is used in Decoded String at Index?
The problem mainly relies on string traversal and arithmetic on lengths rather than heavy data structures. Conceptually it resembles stack unwinding because repeated segments are processed in reverse, but the optimal implementation uses only integer variables and the input string.
What is the time complexity of Decoded String at Index?
The optimal algorithms run in O(n) time where n is the length of the encoded string. The solution scans the string once to compute decoded length and once more in reverse to locate the target character. Space complexity remains O(1) because only a few counters are stored.

Ready to solve this problem?

Practice Decoded String at Index with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring