3307. Find the K-th 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 ith
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 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.
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 <= 1014
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)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|