Number of prefix connected groups

Array Hash Table String Counting

60.5% acceptance

Mar 15, 2026

You are given an array of strings words and an integer k. Two words a and b at distinct indices are prefix-connected if a[0..k-1] == b[0..k-1]. A connected group is a set of words such that each pair of words is prefix-connected. Return the number of connected groups that contain at least two words, formed from the given words.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn prefix_connected(words: Vec<String>, k: i32) -> i32 {
    use std::collections::HashMap;
    let k = k as usize;
    let mut groups: HashMap<String, i32> = HashMap::new();
    for word in &words {
      if word.len() >= k {
        let prefix = word[..k].to_string();
        *groups.entry(prefix).or_insert(0) += 1;
      }
    }
    groups.values().filter(|&&cnt| cnt >= 2).count() as i32
  }
}