Strings differ by one character

use std::collections::HashSet;

impl Solution {
  pub fn differ_by_one(dict: Vec<String>) -> bool {
    // Rolling hash approach: for each position, hash the string with that char replaced by wildcard
    let n = dict.len();
    if n == 0 { return false; }
    let m = dict[0].len();
    let modp: u64 = (1u64 << 61) - 1; // Mersenne prime
    let base: u64 = 31;
    
    // For each position j, create a hash that skips character at j
    // hash_without_j = hash - char_j * base^(m-1-j)
    // If two strings have the same hash_without_j for the same j, they differ by at most 1 char at position j
    
    let bytes: Vec<&[u8]> = dict.iter().map(|s| s.as_bytes()).collect();
    
    // Precompute powers of base
    let mut pow = vec![1u64; m + 1];
    for i in 1..=m {
      pow[i] = mul_mod(pow[i - 1], base, modp);
    }
    
    // Compute full hash for each string
    let mut full_hash = vec![0u64; n];
    for i in 0..n {
      let mut h = 0u64;
      for j in 0..m {
        h = add_mod(mul_mod(h, base, modp), (bytes[i][j] - b'a' + 1) as u64, modp);
      }
      full_hash[i] = h;
    }
    
    // For each position j, compute hash without position j and check for collisions
    for j in 0..m {
      let mut seen = HashSet::new();
      for i in 0..n {
        let char_contrib = mul_mod((bytes[i][j] - b'a' + 1) as u64, pow[m - 1 - j], modp);
        let h = sub_mod(full_hash[i], char_contrib, modp);
        if !seen.insert((h, j)) {
          // Verify: find the other string with same hash
          for k in 0..i {
            let char_contrib_k = mul_mod((bytes[k][j] - b'a' + 1) as u64, pow[m - 1 - j], modp);
            let hk = sub_mod(full_hash[k], char_contrib_k, modp);
            if hk == h {
              // Verify they actually differ by exactly 1
              let diffs = (0..m).filter(|&p| bytes[i][p] != bytes[k][p]).count();
              if diffs == 1 {
                return true;
              }
            }
          }
        }
      }
    }
    false
  }
}

fn mul_mod(a: u64, b: u64, m: u64) -> u64 {
  ((a as u128 * b as u128) % m as u128) as u64
}

fn add_mod(a: u64, b: u64, m: u64) -> u64 {
  let s = a + b;
  if s >= m { s - m } else { s }
}

fn sub_mod(a: u64, b: u64, m: u64) -> u64 {
  if a >= b { a - b } else { a + m - b }
}