Welcome to Subscribe On Youtube
3307. Find the Kth Character in String Game II
Description
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 i^{th}
operation.
Now Bob will ask Alice to perform all operations in sequence:
 If
operations[i] == 0
, append a copy ofword
to itself.  If
operations[i] == 1
, generate a new string by changing each character inword
to its next character in the English alphabet, and append it to the originalword
. For example, performing the operation on"c"
generates"cd"
and performing the operation on"zb"
generates"zbac"
.
Return the value of the k^{th}
character in word
after performing all the operations.
Note that the character 'z'
can be changed to 'a'
in the second type of operation.
Example 1:
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 <= 10^{14}
1 <= operations.length <= 100
operations[i]
is either 0 or 1. The input is generated such that
word
has at leastk
characters after all operations.
Solutions
Solution 1: Recurrence
Since the length of the string doubles after each operation, if we perform $i$ operations, the length of the string will be $2^i$.
We can simulate this process to find the first string length $n$ that is greater than or equal to $k$.
Next, we backtrack and discuss the following cases:
 If $k \gt n / 2$, it means $k$ is in the second half. If $\textit{operations}[i  1] = 1$, it means the character at position $k$ is obtained by adding $1$ to the character in the first half. We add $1$ to it. Then we update $k$ to $k  n / 2$.
 If $k \le n / 2$, it means $k$ is in the first half and is not affected by $\textit{operations}[i  1]$.
 Next, we update $n$ to $n / 2$ and continue backtracking until $n = 1$.
Finally, we take the resulting number modulo $26$ and add the ASCII code of 'a'
to get the answer.
The time complexity is $O(\log k)$, and the space complexity is $O(1)$.

class Solution { public char kthCharacter(long k, int[] operations) { long n = 1; int i = 0; while (n < k) { n *= 2; ++i; } int d = 0; while (n > 1) { if (k > n / 2) { k = n / 2; d += operations[i  1]; } n /= 2; i; } return (char) ('a' + (d % 26)); } }

class Solution { public: char kthCharacter(long long k, vector<int>& operations) { long long n = 1; int i = 0; while (n < k) { n *= 2; ++i; } int d = 0; while (n > 1) { if (k > n / 2) { k = n / 2; d += operations[i  1]; } n /= 2; i; } return 'a' + (d % 26); } };

class Solution: def kthCharacter(self, k: int, operations: List[int]) > str: n, i = 1, 0 while n < k: n *= 2 i += 1 d = 0 while n > 1: if k > n // 2: k = n // 2 d += operations[i  1] n //= 2 i = 1 return chr(d % 26 + ord("a"))

func kthCharacter(k int64, operations []int) byte { n := int64(1) i := 0 for n < k { n *= 2 i++ } d := 0 for n > 1 { if k > n/2 { k = n / 2 d += operations[i1] } n /= 2 i } return byte('a' + (d % 26)) }

function kthCharacter(k: number, operations: number[]): string { let n = 1; let i = 0; while (n < k) { n *= 2; i++; } let d = 0; while (n > 1) { if (k > n / 2) { k = n / 2; d += operations[i  1]; } n /= 2; i; } return String.fromCharCode('a'.charCodeAt(0) + (d % 26)); }