Find the k th character in string game ii

Math Bit Manipulation Recursion

48.5% acceptance

Feb 23, 2026

524

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 ith operation. Now Bob will ask Alice to perform all operations in sequence: If operations[i] == 0, append a copy of word to itself. If operations[i] == 1, 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 performing all the operations. Note that the character 'z' can be changed to 'a' in the second type of operation.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn kth_character(k: i64, operations: Vec<i32>) -> char {
    // After each operation, word doubles in length.
    // We track the position k (0-indexed) and count how many type-1 ops contributed.
    let mut k = k - 1; // 0-indexed
    let mut shifts = 0i64;
    // Compute sizes after each operation
    let mut sizes = vec![1i64];
    for &op in &operations {
      let last = *sizes.last().unwrap();
      sizes.push(last.saturating_mul(2));
      let _ = op;
    }
    // Walk back: at each step, if k >= sizes[i], then it's in the second half
    for i in (0..operations.len()).rev() {
      let half = sizes[i];
      if k >= half {
        k -= half;
        if operations[i] == 1 {
          shifts += 1;
        }
      }
    }
    (b'a' + (shifts % 26) as u8) as char
  }
}