Find the K-th Character in String Game I solution and explanation
Google
9 more videos on this problem
Find the K-th Character in String Game I | Two Approaches | Leetcode 3304 | codestorywithMIKcodestorywithMIK · 17:39 · 8K views
3304. Find the K-th Character in String Game I (Leetcode Easy)Programming Live with Larry · 5:01 · 1K views
Leetcode 3304. Find the K-th Character in String Game I | Elegant Log-Based Python SolutionStatLearn Tech · 13:39 · 1K views
Daily Leetcode #1920: Jul 03, 2025 - 3304. Find the K-th Character in String Game IProgramming Live with Larry · 4:50 · 1K views
3304. Find the K-th Character in String Game I | Leetcode Daily - PythonLeetcode Daily · 4:44 · 969 views
3304. Find the K-th Character in String Game I #leetcode #javaprogramming #dsa #dsalgo #stringsCodeVia · 2:44 · 933 views
Find the K th Character in String Game I | LeetCode 3304 | Easy | Simulation / Math / Recursion /Code Harmony · 29:03 · 654 views
3304. Find the K-th Character in String Game I | leetcode 3304 | Iterative & Optimised Java SolutioncodingX krishna · 24:17 · 413 views
Find the K th Character in String Game I | LeetCode 3304 - Pythonimpoldev · 4:35 · 328 views
3304 Find the K th Character in String Game I | LeetCodeR Sai Siddhu · 4:12 · 120 views
The problem
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",wordbecomes"ab". - Generated string is
"bc",wordbecomes"abbc". - Generated string is
"bccd",wordbecomes"abbcbccd".
Example 2:
Input: k = 10
Output: "c"
Constraints:
1 <= k <= 500
Approach overview
Problem Overview: You start with the string "a". In each round, append a new string formed by shifting every character of the current string to the next alphabet letter (a → b, b → c, etc.). The process doubles the string length every step. Given k, return the k-th character in the final infinite sequence.
Approach 1: Brute Force Simulation (Time: O(k), Space: O(k))
Directly simulate the process. Start with s = "a". For each step, generate a second string by iterating through s and shifting every character by one position in the alphabet. Append this new string to the original. Continue until the length of s becomes at least k, then return s[k-1]. This approach mirrors the problem statement and works well for small k. However, the string doubles every round, so memory and runtime grow quickly. It mainly serves as a baseline simulation using simple iteration and character transformation.
Approach 2: Optimized Pattern Recognition (Bit Manipulation) (Time: O(1), Space: O(1))
Instead of constructing the string, observe how characters evolve across rounds. Every time a character moves into the appended half of the string, it gets shifted by one alphabet step. The number of such shifts for position k equals the number of times you move into the "generated" half during recursive splitting of the sequence. This pattern directly corresponds to the number of set bits in k - 1. Compute popcount(k - 1) and shift 'a' forward by that many positions to get the answer. This reduces the problem to a simple bit manipulation operation combined with a small math observation.
This insight can also be derived through recursion. Each round doubles the string. If k lies in the first half, the character is identical to the previous round. If it lies in the second half, the answer is the corresponding first-half character shifted by one. Repeating this logic collapses the problem into counting how many "second-half" transitions occur.
Recommended for interviews: The optimized pattern recognition approach is what interviewers expect. The brute force simulation demonstrates that you understand the string construction process, but recognizing the binary pattern and using popcount(k - 1) shows stronger algorithmic insight and familiarity with simulation optimization.
Approach 1: Brute Force Simulation
In this approach, we simulate each operation manually until the length of the generated word is at least k.
The operation consists of generating the next character for each character in the current string, appending it to the original string, and repeating until the length requirement is met.
def findKthCharacter(k):
word = 'a'
while len(word) < k:
new_word = ''.join(chr((ord(c) - 97 + 1) % 26 + 97) for c in word)
word += new_word
return word[k - 1]
k = 5 # Example input
print(findKthCharacter(k))public class Main {
public static char findKthCharacter(int k) {
StringBuilder word = new StringBuilder("a");
while (word.length() < k) {
StringBuilder newWord = new StringBuilder();
for (int i = 0; i < word.length(); i++) {
char nextChar = (word.charAt(i) == 'z') ? 'a' : (char) (word.charAt(i) + 1);
newWord.append(nextChar);
}
word.append(newWord);
}
return word.charAt(k - 1);
}
public static void main(String[] args) {
int k = 5;
System.out.println(findKthCharacter(k));
}
}#include <iostream>
#include <string>
char findKthCharacter(int k) {
std::string word = "a";
while (word.size() < k) {
std::string new_word;
for (char c : word) {
new_word.push_back((c == 'z') ? 'a' : c + 1);
}
word.append(new_word);
}
return word[k-1];
}
int main() {
int k = 5;
std::cout << findKthCharacter(k) << std::endl;
return 0;
}function findKthCharacter(k) {
let word = 'a';
while (word.length < k) {
let newWord = '';
for (let i = 0; i < word.length; i++) {
newWord += (word[i] === 'z' ? 'a' : String.fromCharCode(word.charCodeAt(i) + 1));
}
word += newWord;
}
return word[k - 1];
}
const k = 5; // Example input
console.log(findKthCharacter(k));#include <stdio.h>
#include <string.h>
char findKthCharacter(int k) {
char word[1000] = "a";
int length = 1;
while (length < k) {
char new_word[1000] = "";
// Append next character for each in the word
for (int i = 0; i < length; i++) {
new_word[i] = (word[i] == 'z') ? 'a' : word[i] + 1;
}
strcpy(new_word + length, word);
// Update the word
strcpy(word, new_word);
length *= 2;
}
return word[k-1];
}
int main() {
int k = 5; // Example input
printf("%c\n", findKthCharacter(k));
return 0;
}using System;
class Program
{
static char FindKthCharacter(int k)
{
string word = "a";
while (word.Length < k)
{
string newWord = string.Empty;
foreach (char c in word)
{
char nextChar = (c == 'z') ? 'a' : (char)(c + 1);
newWord += nextChar;
}
word += newWord;
}
return word[k - 1];
}
static void Main()
{
int k = 5;
Console.WriteLine(FindKthCharacter(k));
}
}Python's string manipulation capabilities are harnessed here to create a new computed string and append it until the word's length meets the required k length.
Time Complexity: O(n^2) - where each extension doubles the length of the string.
Space Complexity: O(n) - requiring storage for the progressively longer strings.
Approach 2: Optimized Pattern Recognition
Given the behavior of the operation, the process generates a pattern in intervals, each effectively doubling the previous string's influence on the final result.
This approach focuses on finding the length of the prefix that must be completed before the k-th character appears in the sequence.
def findKthCharacter(k):
shift = 0
while k > (1 << shift):
k -= (1 << shift)
shift += 1
return chr(97 + ((k - 1) % (1 << shift)))
k = 5 # Example input
print(findKthCharacter(k))public class Main {
public static char findKthCharacter(int k) {
int shift = 0;
while (k > (1 << shift)) {
k -= (1 << shift);
shift++;
}
return (char) ('a' + ((k - 1) % (1 << shift)));
}
public static void main(String[] args) {
int k = 5;
System.out.println(findKthCharacter(k));
}
}#include <iostream>
char findKthCharacter(int k) {
int shift = 0;
while (k > (1 << shift)) {
k -= (1 << shift++);
}
return 'a' + ((k - 1) % (1 << shift));
}
int main() {
int k = 5;
std::cout << findKthCharacter(k) << std::endl;
return 0;
}function findKthCharacter(k) {
let shift = 0;
while (k > (1 << shift)) {
k -= (1 << shift);
shift++;
}
return String.fromCharCode(97 + ((k - 1) % (1 << shift)));
}
const k = 5; // Example input
console.log(findKthCharacter(k));#include <stdio.h>
char findKthCharacter(int k) {
int shift = 0;
int index = 0;
// Find the segment and shift value where k-th character is located
while (k > (1 << shift)) {
k -= (1 << shift);
shift++;
}
index = (k - 1) % (1 << (shift));
return 'a' + (index % 26);
}
int main() {
int k = 5; // Example input
printf("%c\n", findKthCharacter(k));
return 0;
}using System;
class Program
{
static char FindKthCharacter(int k)
{
int shift = 0;
while (k > (1 << shift)) {
k -= (1 << shift);
shift++;
}
return (char)('a' + ((k - 1) % (1 << shift)));
}
static void Main()
{
int k = 5;
Console.WriteLine(FindKthCharacter(k));
}
}Using inherent Python capabilities, string segments are defined and limited, preserving character cycle transitions by segmental positioning till resolution.
Time Complexity: O(log k) - inherent loop compression divided by powers of two yields logarithmic mannerism.
Space Complexity: O(1) - unaccompanied operation sans extensive dynamic calculations.
Approach 3: Simulation
We can use an array word to store the string after each operation. When the length of word is less than k, we continuously perform operations on word.
Finally, return word[k - 1].
The time complexity is O(k), and the space complexity is O(k). Here, k is the input parameter.
function kthCharacter(k: number): string {
const word: number[] = [0];
while (word.length < k) {
word.push(...word.map(x => (x + 1) % 26));
}
return String.fromCharCode(97 + word[k - 1]);
}func kthCharacter(k int) byte {
word := []int{0}
for len(word) < k {
m := len(word)
for i := 0; i < m; i++ {
word = append(word, (word[i]+1)%26)
}
}
return 'a' + byte(word[k-1])
}impl Solution {
pub fn kth_character(k: i32) -> char {
let mut word = vec![0];
while word.len() < k as usize {
let m = word.len();
for i in 0..m {
word.push((word[i] + 1) % 26);
}
}
(b'a' + word[(k - 1) as usize] as u8) as char
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Simulation | Time Complexity: O(n^2) - where each extension doubles the length of the string. Space Complexity: O(n) - requiring storage for the progressively longer strings. |
| Optimized Pattern Recognition | Time Complexity: O(log k) - inherent loop compression divided by powers of two yields logarithmic mannerism. Space Complexity: O(1) - unaccompanied operation sans extensive dynamic calculations. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(k) | O(k) | Useful for understanding the string-building process or when k is very small |
| Optimized Pattern Recognition (Bit Manipulation) | O(1) | O(1) | Best approach for interviews and large k; avoids building the exponential string |
Frequently asked questions
Is Find the K-th Character in String Game I easy or hard?
The problem is labeled Easy with an acceptance rate above 80%. The simulation approach is straightforward, but recognizing the bit manipulation pattern makes it significantly more efficient and demonstrates stronger problem-solving insight.
Find the K-th Character in String Game I Python/Java solution
Most Python and Java solutions implement the optimized approach by computing the number of set bits in k−1. In Python, use bin(k-1).count('1') or bit_count(). In Java, use Integer.bitCount(k-1). The result shifts 'a' forward by that count.
How to solve Find the K-th Character in String Game I in O(1)?
Use a mathematical observation: each time a position falls into the second half of a generated string, the character shifts by one alphabet step. The number of such shifts equals the popcount of k−1 in binary. Compute popcount(k−1) and add that value to 'a' to get the answer in constant time.
What is the best approach for Find the K-th Character in String Game I?
The best approach uses bit manipulation and pattern recognition. The k-th character depends on how many times the position falls into the generated half during the doubling process. This equals the number of set bits in k−1. The final character is 'a' shifted forward by popcount(k−1), giving an O(1) time and O(1) space solution.
Is Find the K-th Character in String Game I asked at Google/Amazon/Meta?
Problems combining string simulation with bit manipulation patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require recognizing binary structure in recursive string construction are especially common in algorithm rounds.
What data structure is used in Find the K-th Character in String Game I?
The brute force approach uses simple string construction and iteration. The optimized solution avoids any explicit data structure and instead relies on bit manipulation and mathematical reasoning over the binary representation of k.
What is the time complexity of Find the K-th Character in String Game I?
The brute force simulation takes O(k) time and O(k) space because the string is built until it reaches length k. The optimized solution runs in O(1) time and O(1) space by computing the number of set bits in k−1 and shifting the base character accordingly.