Skip to main content
Talentd

Find Kth Character in Expanded String - Solution & Explanation

MediumPremiumFree on FleetCodeString10 min read
Practice this problem

Problem Statement

You are given a string s consisting of one or more words separated by single spaces. Each word in s consists of lowercase English letters.

We obtain the expanded string t from s as follows:

  • For each word in s, repeat its first character once, then its second character twice, and so on.

For example, if s = "hello world", then t = "heelllllllooooo woorrrllllddddd".

You are also given an integer k, representing a valid index of the string t.

Return the kth character of the string t.

 

Example 1:

Input: s = "hello world", k = 0

Output: "h"

Explanation:

t = "heelllllllooooo woorrrllllddddd". Therefore, the answer is t[0] = "h".

Example 2:

Input: s = "hello world", k = 15

Output: " "

Explanation:

t = "heelllllllooooo woorrrllllddddd". Therefore, the answer is t[15] = " ".

 

Constraints:

  • 1 <= s.length <= 105
  • s contains only lowercase English letters and spaces ' '.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.
  • 0 <= k < t.length. That is, k is a valid index of t.

Approach Overview

Problem Overview: You are given a compressed or encoded string where expansion rules create a much longer final string. The task is to return the kth character of the fully expanded result without explicitly building the entire string.

Approach 1: Full Expansion Simulation (O(n * m) time, O(n * m) space)

The most straightforward method is to simulate the expansion directly. Iterate through the input string, append characters, and repeat segments when digits indicate expansion. After constructing the full string, return the character at index k - 1. This approach is simple to reason about but quickly becomes impractical when the expanded string grows to millions or billions of characters. It also consumes significant memory since the entire expanded result must be stored.

Approach 2: Math + Length Simulation (O(n) time, O(1) space)

The efficient strategy avoids building the expanded string. Instead, track the length of the string that would result from expansion. Iterate through the encoded string and update a running length: letters increase the length by one, while digits multiply the current length because they repeat the existing sequence. Once the simulated length reaches or exceeds k, traverse the string backward. Reduce k using modulo operations when encountering repetition and decrease the length when stepping past characters. When k matches a character position, you’ve found the answer.

This works because repetition does not change character order—only how many times a prefix appears. Tracking length mathematically lets you map the kth position in the expanded string back to a position in the original encoded sequence.

Problems like this are common in string processing where expansion rules produce massive outputs. The trick is recognizing that the output size can exceed memory limits, which pushes you toward a math-based reasoning approach combined with careful simulation of lengths rather than characters.

Recommended for interviews: The Math + Simulation approach. Interviewers expect you to recognize that full expansion is infeasible for large inputs. Demonstrating the brute force idea shows baseline understanding, but deriving the length-tracking method shows strong problem-solving and complexity awareness.

Solution

We first split the string s into multiple words by spaces. For each word w, we can calculate the length it occupies in the expanded string t as m=\frac{(1+|w|)cdot |w|}{2}.

If k = m, it means the k-th character is a space, and we can directly return a space.

If k > m, it means the k-th character is not in the expanded part of the current word. We subtract the expanded length m of the current word and the space length 1 from k, and continue processing the next word.

Otherwise, the k-th character is in the expanded part of the current word. We can find the k-th character by simulating the expansion process:

  • Initialize a variable cur = 0 to represent the number of characters that have been expanded so far.
  • Iterate through each character w[i] of the word w:
    • Increase cur by i + 1.
    • If k < cur, it means the k-th character is w[i], and we return this character.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Full Expansion SimulationO(n * m)O(n * m)Small inputs where expanded size remains manageable
Math + Length SimulationO(n)O(1)Large expansions where building the full string is impossible

Video Solution

Find Kth Character in Expanded String • Owen Wu • 2 views views

Frequently Asked Questions

Is Find Kth Character in Expanded String easy or hard?
This problem is typically rated Medium because the brute force idea is simple but fails for large expansions. The challenge is recognizing that you must simulate string length mathematically and trace the kth position backward without building the expanded string.
Find Kth Character in Expanded String Python/Java solution
Most implementations follow the same two-pass logic. First compute the expanded length while scanning the string. Then traverse backward, updating k with modulo when encountering repetition and decreasing length when stepping past characters. This pattern translates cleanly to Python, Java, C++, Go, and TypeScript.
How to solve Find Kth Character in Expanded String in O(n)?
Scan the string while maintaining the length of the expanded result. Letters increase the length by one, and digits multiply the current length. Once the total length reaches or exceeds k, iterate backward through the string, shrinking the simulated length and adjusting k with modulo operations until the exact character is identified.
What is the best approach for Find Kth Character in Expanded String?
The most efficient approach is Math + Simulation. Instead of constructing the expanded string, track the length of the string as expansion rules are processed. Once the simulated length reaches k, traverse backward and use modulo operations to map the kth position to its original character. This runs in O(n) time and O(1) space.
Is Find Kth Character in Expanded String asked at Google/Amazon/Meta?
String expansion and kth-position queries appear in interviews at companies like Google, Amazon, and Meta. Variants such as 'Decoded String at Index' follow the same idea of tracking expansion length mathematically instead of constructing the full string.
What data structure is used in Find Kth Character in Expanded String?
The optimal approach primarily uses arithmetic with a running length variable and index traversal. No complex data structure is required—just string iteration and mathematical reasoning to map the kth index back to the original encoded characters.
What is the time complexity of Find Kth Character in Expanded String?
The optimal solution runs in O(n) time where n is the length of the encoded string. It performs a forward pass to compute the expanded length and a backward pass to locate the kth character. Space complexity is O(1) since no expanded string is stored.

Ready to solve this problem?

Practice Find Kth Character in Expanded String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring