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 i^th operation.
Now Bob will ask Alice to perform all operations in sequence:
- If
operations[i] == 0, append a copy ofwordto itself. - If
operations[i] == 1, generate a new string by changing each character inwordto its next character in the English alphabet, and append it to the originalword.
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"After three copy-append operations,
word becomes "aaaaaaaa", so the 5th character is "a".Example 2
Input
k = 10, operations = [0,1,0,1]Output
"b"After all operations,
word becomes "aabbaabbbbccbbcc", so the 10th character is "b".Constraints
- 1 <= k <= 10^14
- 1 <= operations.length <= 100
- operations[i] is either 0 or 1.
- The input is generated such that
wordhas at leastkcharacters after all operations.