Watch 10 video solutions for Find the K-th Character in String Game I, a easy level problem involving Math, Bit Manipulation, Recursion. This walkthrough by codestorywithMIK has 8,188 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |