Groups of strings

Array Hash Table String Bit Manipulation Union-Find

27.5% acceptance

Feb 25, 2026

507

You are given a 0-indexed array of strings words where no letter occurs more than once in any string. Two strings s1 and s2 are connected if the set of letters of s2 can be obtained from s1 by: adding exactly one letter, deleting exactly one letter, or replacing exactly one letter. Return [max_groups, size_of_largest_group].

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

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

    let mut mask_count: HashMap<u32, i32> = HashMap::new();
    for word in &words {
      let mask: u32 = word.bytes().fold(0, |acc, b| acc | (1 << (b - b'a')));
      *mask_count.entry(mask).or_insert(0) += 1;
    }

    let masks: Vec<u32> = mask_count.keys().cloned().collect();
    let n = masks.len();
    let mask_to_idx: HashMap<u32, usize> = masks.iter().enumerate().map(|(i, &m)| (m, i)).collect();
    let mut parent: Vec<usize> = (0..n).collect();
    let mut size: Vec<i32> = masks.iter().map(|&m| mask_count[&m]).collect();

    fn find(parent: &mut [usize], x: usize) -> usize {
      let mut x = x;
      while parent[x] != x {
        parent[x] = parent[parent[x]];
        x = parent[x];
      }
      x
    }

    let do_union = |parent: &mut Vec<usize>, size: &mut Vec<i32>, x: usize, y: usize| {
      let (px, py) = (find(parent, x), find(parent, y));
      if px != py {
        if size[px] >= size[py] {
          parent[py] = px;
          size[px] += size[py];
        } else {
          parent[px] = py;
          size[py] += size[px];
        }
      }
    };

    for i in 0..n {
      let mask = masks[i];
      for bit in 0..26u32 {
        if mask & (1 << bit) != 0 {
          // Delete operation
          let del = mask ^ (1 << bit);
          if let Some(&j) = mask_to_idx.get(&del) {
            do_union(&mut parent, &mut size, i, j);
          }
          // Replace operation: delete bit, add bit2
          for bit2 in 0..26u32 {
            if mask & (1 << bit2) == 0 {
              let rep = del | (1 << bit2);
              if let Some(&j) = mask_to_idx.get(&rep) {
                do_union(&mut parent, &mut size, i, j);
              }
            }
          }
        } else {
          // Add operation
          let add = mask | (1 << bit);
          if let Some(&j) = mask_to_idx.get(&add) {
            do_union(&mut parent, &mut size, i, j);
          }
        }
      }
    }

    let num_groups = (0..n).filter(|&i| find(&mut parent, i) == i).count() as i32;
    let max_size = *size.iter().max().unwrap_or(&0);
    vec![num_groups, max_size]
  }
}