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 <= 500In 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log k) - because each step reduces 'k' by a power of two.
Space Complexity: O(1) - independent of string simulation.
| 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. |
1 secret trick to get better at Leetcode! • Top SWE • 21,586 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