Is Find the K-th Character in String Game I easy or hard?

The problem is labeled Easy with an acceptance rate above 80%. The simulation approach is straightforward, but recognizing the bit manipulation pattern makes it significantly more efficient and demonstrates stronger problem-solving insight.

Find the K-th Character in String Game I Python/Java solution

Most Python and Java solutions implement the optimized approach by computing the number of set bits in k−1. In Python, use bin(k-1).count('1') or bit_count(). In Java, use Integer.bitCount(k-1). The result shifts 'a' forward by that count.

How to solve Find the K-th Character in String Game I in O(1)?

Use a mathematical observation: each time a position falls into the second half of a generated string, the character shifts by one alphabet step. The number of such shifts equals the popcount of k−1 in binary. Compute popcount(k−1) and add that value to 'a' to get the answer in constant time.

What is the best approach for Find the K-th Character in String Game I?

The best approach uses bit manipulation and pattern recognition. The k-th character depends on how many times the position falls into the generated half during the doubling process. This equals the number of set bits in k−1. The final character is 'a' shifted forward by popcount(k−1), giving an O(1) time and O(1) space solution.

Is Find the K-th Character in String Game I asked at Google/Amazon/Meta?

Problems combining string simulation with bit manipulation patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require recognizing binary structure in recursive string construction are especially common in algorithm rounds.

What data structure is used in Find the K-th Character in String Game I?

The brute force approach uses simple string construction and iteration. The optimized solution avoids any explicit data structure and instead relies on bit manipulation and mathematical reasoning over the binary representation of k.

What is the time complexity of Find the K-th Character in String Game I?

The brute force simulation takes O(k) time and O(k) space because the string is built until it reaches length k. The optimized solution runs in O(1) time and O(1) space by computing the number of set bits in k−1 and shifting the base character accordingly.

Description Hints 1 Solution Video 17:39

3304. Find the K-th Character in String Game I

Easy81.6% acceptance5 companies

Alice and Bob are playing a game. Initially, Alice has a string word = "a".

You are given a positive integer k.

Now Bob will ask Alice to perform the following operation forever:

Generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word.

For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac".

Return the value of the k^th character in word, after enough operations have been done for word to have at least k characters.

Note that the character 'z' can be changed to 'a' in the operation.

Example 1:

Input: k = 5

Output: "b"

Explanation:

Initially, word = "a". We need to do the operation three times:

Generated string is "b", word becomes "ab".
Generated string is "bc", word becomes "abbc".
Generated string is "bccd", word becomes "abbcbccd".

Example 2:

Input: k = 10

Output: "c"

Constraints:

1 <= k <= 500

Asked at 5 companies

Google Amazon Meta Bloomberg Microsoft

Topics

Hints open one at a time

Hint 1

The constraints are small. Construct the string by simulating the operations.

17:39

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution