3307. Find the K-th Character in String Game II LeetCode Solution
In this guide, you will get 3307. Find the K-th Character in String Game II LeetCode Solution with the best time and space complexity. The solution to Find the K-th Character in String Game II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the K-th Character in String Game II
Alice and Bob are playing a game. Initially, Alice has a string word = “a”.
You are given a positive integer k. You are also given an integer array operations, where operations[i] represents the type of the ith operation.
Now Bob will ask Alice to perform all operations in sequence:
If operations[i] == 0, append a copy of word to itself.
If operations[i] == 1, 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 performing all the operations.
Note that the character ‘z’ can be changed to ‘a’ in the second type of operation.
Input: k = 5, operations = [0,0,0]
Output: “a”
Explanation:
Initially, word == “a”. Alice performs the three operations as follows:
Appends “a” to “a”, word becomes “aa”.
Appends “aa” to “aa”, word becomes “aaaa”.
Appends “aaaa” to “aaaa”, word becomes “aaaaaaaa”.
Example 2:
Input: k = 10, operations = [0,1,0,1]
Output: “b”
Explanation:
Initially, word == “a”. Alice performs the four operations as follows:
Appends “a” to “a”, word becomes “aa”.
Appends “bb” to “aa”, word becomes “aabb”.
Appends “aabb” to “aabb”, word becomes “aabbaabb”.
Appends “bbccbbcc” to “aabbaabb”, word becomes “aabbaabbbbccbbcc”.
Constraints:
1 <= k <= 1014
1 <= operations.length <= 100
operations[i] is either 0 or 1.
The input is generated such that word has at least k characters after all operations.
Complexity Analysis
Time Complexity: O(\log k)
Space Complexity: O(1)
3307. Find the K-th Character in String Game II LeetCode Solution in C++
class Solution {
public:
char kthCharacter(long long k, vector<int>& operations) {
const int operationsCount = ceil(log2(k));
int increases = 0;
for (int i = operationsCount - 1; i >= 0; --i) {
const long halfSize = 1L << i;
if (k > halfSize) {
k -= halfSize; // Move k from the right half to the left half.
increases += operations[i];
}
}
return 'a' + increases % 26;
}
}; /* code provided by PROGIEZ */
3307. Find the K-th Character in String Game II LeetCode Solution in Java
class Solution {
public char kthCharacter(long k, int[] operations) {
final int operationsCount = (int) Math.ceil(Math.log(k) / Math.log(2));
int increases = 0;
for (int i = operationsCount - 1; i >= 0; --i) {
final long halfSize = 1L << i;
if (k > halfSize) {
k -= halfSize; // Move k from the right half to the left half.
increases += operations[i];
}
}
return (char) ('a' + increases % 26);
}
} // code provided by PROGIEZ
3307. Find the K-th Character in String Game II LeetCode Solution in Python
class Solution:
def kthCharacter(self, k: int, operations: list[int]) -> str:
operationsCount = math.ceil(math.log2(k))
increases = 0
for i in range(operationsCount - 1, -1, -1):
halfSize = 2**i
if k > halfSize:
k -= halfSize # Move k from the right half to the left half.
increases += operations[i]
return string.ascii_lowercase[increases % 26] # code by PROGIEZ
