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:
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:
"b", word becomes "ab"."bc", word becomes "abbc"."bccd", word becomes "abbcbccd".Example 2:
Input: k = 10
Output: "c"
Constraints:
1 <= k <= 500Problem 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.
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.
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.
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.
Time Complexity: O(log k) - because each step reduces 'k' by a power of two.
Space Complexity: O(1) - independent of string 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.
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(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 |
Find the K-th Character in String Game I | Two Approaches | Leetcode 3304 | codestorywithMIK • codestorywithMIK • 8,188 views views
Watch 9 more video solutions →Practice Find the K-th Character in String Game I with our built-in code editor and test cases.
Practice on FleetCode