Count pairs of similar strings

Array Hash Table String Bit Manipulation Counting

73.6% acceptance

Feb 25, 2026

586

You are given a 0-indexed string array words. Two strings are similar if they consist of the same characters. For example, "abca" and "cba" are similar since both consist of characters 'a', 'b', and 'c'. However, "abacba" and "bcfd" are not similar since they do not consist of the same characters. Return the number of pairs (i, j) such that 0 <= i < j <= word.length - 1 and the two strings words[i] and words[j] are similar.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn similar_pairs(words: Vec<String>) -> i32 {
    use std::collections::HashMap;
    let mut counts: HashMap<u32, i32> = HashMap::new();
    for w in &words {
      let mask: u32 = w.bytes().fold(0u32, |acc, b| acc | (1 << (b - b'a')));
      *counts.entry(mask).or_insert(0) += 1;
    }
    counts.values().map(|&c| c * (c - 1) / 2).sum()
  }
}