Count caesar cipher pairs

Array Hash Table Math String Counting

50.9% acceptance

Mar 16, 2026

105

You are given an array words of n strings. Each string has length m and contains only lowercase English letters. Two strings s and t are similar if we can apply the following operation any number of times (possibly zero times) so that s and t become equal. Choose either s or t. Replace every letter in the chosen string with the next letter in the alphabet cyclically. The next letter after 'z' is 'a'. Count the number of pairs of indices (i, j) such that: i < j words[i] and words[j] are similar. Return an integer denoting the number of such pairs.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs(words: Vec<String>) -> i64 {
    use std::collections::HashMap;

    // Two words are similar if one can be shifted to match the other.
    // This means for words s and t, there exists some shift k such that
    // for all positions p: (s[p] + k) % 26 == t[p].
    // Equivalently, for all positions p: (s[p] - s[0]) % 26 == (t[p] - t[0]) % 26.
    // So we normalize each word by computing differences from the first character.

    let mut map: HashMap<Vec<u8>, i64> = HashMap::new();

    for word in &words {
      let bytes = word.as_bytes();
      let first = bytes[0];
      let key: Vec<u8> = bytes.iter().map(|&b| (b + 26 - first) % 26).collect();
      *map.entry(key).or_insert(0) += 1;
    }

    let mut result = 0i64;
    for &count in map.values() {
      result += count * (count - 1) / 2;
    }

    result
  }
}