Welcome to Subscribe On Youtube

3839. Number of Prefix Connected Groups

Description

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.

Note:

  • Words with length less than k cannot join any group and are ignored.
  • Duplicate strings are treated as separate words.

 

Example 1:

Input: words = ["apple","apply","banana","bandit"], k = 2

Output: 2

Explanation:

Words sharing the same first k = 2 letters are grouped together:

  • words[0] = "apple" and words[1] = "apply" share prefix "ap".
  • words[2] = "banana" and words[3] = "bandit" share prefix "ba".

Thus, there are 2 connected groups, each containing at least two words.

Example 2:

Input: words = ["car","cat","cartoon"], k = 3

Output: 1

Explanation:

Words are evaluated for a prefix of length k = 3:

  • words[0] = "car" and words[2] = "cartoon" share prefix "car".
  • words[1] = "cat" does not share a 3-length prefix with any other word.

Thus, there is 1 connected group.

Example 3:

Input: words = ["bat","dog","dog","doggy","bat"], k = 3

Output: 2

Explanation:

Words are evaluated for a prefix of length k = 3:

  • words[0] = "bat" and words[4] = "bat" form a group.
  • words[1] = "dog", words[2] = "dog" and words[3] = "doggy" share prefix "dog".

Thus, there are 2 connected groups, each containing at least two words.

 

Constraints:

  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 100
  • 1 <= k <= 100
  • All strings in words consist of lowercase English letters.

Solutions

Solution 1: Hash Table

We use a hash table $\textit{cnt}$ to count the number of occurrences of the prefix composed of the first $k$ characters of each string with length greater than or equal to $k$. Finally, we count the number of keys in $\textit{cnt}$ with values greater than $1$, which is the number of connected groups.

The time complexity is $O(n \times k)$, and the space complexity is $O(n)$, where $n$ is the length of $\textit{words}$.

  • class Solution {
    public int prefixConnected(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<>();
        for (var w : words) {
            if (w.length() >= k) {
                cnt.merge(w.substring(0, k), 1, Integer::sum);
            }
        }
        int ans = 0;
        for (var v : cnt.values()) {
            if (v > 1) {
                ++ans;
            }
        }
        return ans;
    }
}


  • class Solution {
public:
    int prefixConnected(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for (const auto& w : words) {
            if (w.size() >= k) {
                ++cnt[w.substr(0, k)];
            }
        }
        int ans = 0;
        for (const auto& [_, v] : cnt) {
            if (v > 1) {
                ++ans;
            }
        }
        return ans;
    }
};


  • class Solution:
    def prefixConnected(self, words: List[str], k: int) -> int:
        cnt = Counter()
        for w in words:
            if len(w) >= k:
                cnt[w[:k]] += 1
        return sum(v > 1 for v in cnt.values())


  • func prefixConnected(words []string, k int) int {
	cnt := make(map[string]int)
	for _, w := range words {
		if len(w) >= k {
			cnt[w[:k]]++
		}
	}
	ans := 0
	for _, v := range cnt {
		if v > 1 {
			ans++
		}
	}
	return ans
}


  • function prefixConnected(words: string[], k: number): number {
    const cnt = new Map<string, number>();

    for (const w of words) {
        if (w.length >= k) {
            const key = w.substring(0, k);
            cnt.set(key, (cnt.get(key) ?? 0) + 1);
        }
    }

    let ans = 0;
    for (const v of cnt.values()) {
        if (v > 1) {
            ans++;
        }
    }

    return ans;
}

All Problems

All Solutions