Find the k th character in string game i

Math Bit Manipulation Recursion Simulation

81.6% acceptance

Feb 23, 2026

645

136

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 original word. 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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn kth_character(k: i32) -> char {
    // The string grows by doubling; the second half is the first half with each char +1
    // To find the kth char (1-indexed), count how many times we "go into the second half"
    let mut k = k as usize - 1; // 0-indexed
    let mut shifts = 0u32;
    let mut len = 1usize;
    while len <= k {
      len *= 2;
    }
    // Walk back from position k
    while len > 1 {
      len /= 2;
      if k >= len {
        k -= len;
        shifts += 1;
      }
    }
    (b'a' + (shifts % 26) as u8) as char
  }
}