This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
3304. Find the K-th Character in String Game I
Difficulty: Easy
Topics: Math, Bit Manipulation, Recursion, Simulation
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
wordto 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".
- Generated string is
Example 2:
- Input: k = 10
- Output: "c"
Constraints:
1 <= k <= 500
Hint:
- The constraints are small. Construct the string by simulating the operations.
Solution:
We need to find the k-th character in a string that is constructed by repeatedly performing operations where each character in the current string is replaced by its next character in the alphabet (with 'z' wrapping around to 'a'), and this new string is appended to the original string. The initial string is "a".
Approach
- Initialization: Start with the initial string "a".
-
Simulation of Operations: While the length of the current string is less than
k, perform the following operations:- Generate Next String: For each character in the current string, replace it with the next character in the alphabet ('a' follows 'z').
- Append Next String: Append this newly generated string to the original string.
-
Result Extraction: Once the string's length is at least
k, return the k-th character (1-based index) of the constructed string.
This approach efficiently builds the string by simulating each operation step-by-step until the string has at least k characters. Given the constraint that k is at most 500, the maximum length of the string after 9 operations is 512 (29), which is manageable and ensures the solution is efficient.
Let's implement this solution in PHP: 3304. Find the K-th Character in String Game I
<?php
/**
* @param Integer $k
* @return String
*/
function kthCharacter($k) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
echo kthCharacter(5); // Output: b
echo "\n";
echo kthCharacter(10); // Output: c
?>
Explanation:
-
Initialization: The initial string
$sis set to "a". -
Loop Until String Length >= k: The loop continues as long as the length of
$sis less thank.-
Generate Next String (
$t): For each character in$s, the next character in the alphabet is computed. If the character is 'z', it wraps around to 'a'; otherwise, it is incremented to the next character (e.g., 'a' becomes 'b'). -
Append Next String: The generated string
$tis appended to$s, effectively doubling the length of$sin each iteration.
-
Generate Next String (
-
Return k-th Character: Once the loop exits, the k-th character (1-based) is accessed at index
$k - 1in the string$sand returned.
This approach efficiently constructs the string by leveraging the operations described, ensuring that the k-th character is found by directly simulating the process until the string is sufficiently long. The solution handles the character wrapping from 'z' to 'a' and efficiently builds the string in logarithmic time relative to k.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2025-07-03T04:07:00+00:00) 3304. Find the K-th Character in String Game I. Retrieved from https://www.scien.cx/2025/07/03/3304-find-the-k-th-character-in-string-game-i/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.