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.

Description Hints 3 Solution Video 2:06

3744. Find Kth Character in Expanded String

Medium56.4% acceptancePremium elsewhere, free here

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 k^th 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 <= 10⁵
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.

Topics

String

Hints open one at a time

Hint 1

Use the index of a character in the word to calculate how many times it is repeated in t.

Hint 2

Reduce k by that repetition count as you iterate through the characters.

Hint 3

Handle spaces as single characters (cost 1) and reset the index counter for each new word.

2:06

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"hello world"
0

Input

"hello world"
15

Your code is saved on this device.Solution