Skip to content

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}\).

1
2
3
4
5
6
7
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())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
}

Comments