Skip to main content
Talentd

Find the K-th Character in String Game I - Solution & Explanation

EasyMathBit ManipulationRecursionSimulation13 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 kth 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

Approach Overview

Problem Overview: You start with the string "a". In each round, append a new string formed by shifting every character of the current string to the next alphabet letter (a → b, b → c, etc.). The process doubles the string length every step. Given k, return the k-th character in the final infinite sequence.

Approach 1: Brute Force Simulation (Time: O(k), Space: O(k))

Directly simulate the process. Start with s = "a". For each step, generate a second string by iterating through s and shifting every character by one position in the alphabet. Append this new string to the original. Continue until the length of s becomes at least k, then return s[k-1]. This approach mirrors the problem statement and works well for small k. However, the string doubles every round, so memory and runtime grow quickly. It mainly serves as a baseline simulation using simple iteration and character transformation.

Approach 2: Optimized Pattern Recognition (Bit Manipulation) (Time: O(1), Space: O(1))

Instead of constructing the string, observe how characters evolve across rounds. Every time a character moves into the appended half of the string, it gets shifted by one alphabet step. The number of such shifts for position k equals the number of times you move into the "generated" half during recursive splitting of the sequence. This pattern directly corresponds to the number of set bits in k - 1. Compute popcount(k - 1) and shift 'a' forward by that many positions to get the answer. This reduces the problem to a simple bit manipulation operation combined with a small math observation.

This insight can also be derived through recursion. Each round doubles the string. If k lies in the first half, the character is identical to the previous round. If it lies in the second half, the answer is the corresponding first-half character shifted by one. Repeating this logic collapses the problem into counting how many "second-half" transitions occur.

Recommended for interviews: The optimized pattern recognition approach is what interviewers expect. The brute force simulation demonstrates that you understand the string construction process, but recognizing the binary pattern and using popcount(k - 1) shows stronger algorithmic insight and familiarity with simulation optimization.

Approach 1: Brute Force Simulation

In this approach, we simulate each operation manually until the length of the generated word is at least k.

The operation consists of generating the next character for each character in the current string, appending it to the original string, and repeating until the length requirement is met.

This solution initializes the word to "a" and simulates the operations literally by generating a new string and extending it until the length of the word is at least k.

We make use of a buffer to store the new generated word, which includes the transformation of each character in the current word followed by the original word.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) - where n operations are performed, growing the string exponentially.

Space Complexity: O(n) - memory is reallocated as the string grows.

Try this approach in the editor →

Approach 2: Optimized Pattern Recognition

Given the behavior of the operation, the process generates a pattern in intervals, each effectively doubling the previous string's influence on the final result.

This approach focuses on finding the length of the prefix that must be completed before the k-th character appears in the sequence.

The C implementation recognizes that the result of each operation is to effectively double past iterations' influence. By finding the segment where 'k' resides, exact position deciphering is made, hence computing the k-th character directly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log k) - because each step reduces 'k' by a power of two.

Space Complexity: O(1) - independent of string simulation.

Try this approach in the editor →

Approach 3: Simulation

We can use an array word to store the string after each operation. When the length of word is less than k, we continuously perform operations on word.

Finally, return word[k - 1].

The time complexity is O(k), and the space complexity is O(k). Here, k is the input parameter.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Simulation

Time Complexity: O(n^2) - where n operations are performed, growing the string exponentially.

Space Complexity: O(n) - memory is reallocated as the string grows.

Optimized Pattern Recognition

Time Complexity: O(log k) - because each step reduces 'k' by a power of two.

Space Complexity: O(1) - independent of string simulation.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(k)O(k)Useful for understanding the string-building process or when k is very small
Optimized Pattern Recognition (Bit Manipulation)O(1)O(1)Best approach for interviews and large k; avoids building the exponential string

Video Solution

Find the K-th Character in String Game I | Two Approaches | Leetcode 3304 | codestorywithMIK • codestorywithMIK • 8,424 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Find the K-th Character in String Game I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shifting Letters