3304. Find the K-th Character in String Game I
Description
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:
- Generate a new string by changing each character in
word
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 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:
- Generated string is
"b"
,word
becomes"ab"
. - Generated string is
"bc"
,word
becomes"abbc"
. - Generated string is
"bccd"
,word
becomes"abbcbccd"
.
Example 2:
Input: k = 10
Output: "c"
Constraints:
1 <= k <= 500
Solutions
Solution 1: Simulation
We can use an array $\textit{word}$ to store the string after each operation. When the length of $\textit{word}$ is less than $k$, we continuously perform operations on $\textit{word}$.
Finally, return $\textit{word}[k - 1]$.
The time complexity is $O(k)$, and the space complexity is $O(k)$. Here, $k$ is the input parameter.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 |
|