#2157

Groups of Strings

international master · 2045 · lc hard +32 · premium · failed · 27.5% accepted · 507 likes · top 5%

⚑ Disjoint Set Union

Description

You are given a 0-indexed array of strings words. Each string consists only of lowercase English letters with no repeated letter within a word.

Two strings s1 and s2 are connected if the letter set of s2 can be derived from the letter set of s1 by exactly one of:

 - Adding one letter to s1's letters.

 - Removing one letter from s1's letters.

 - Replacing one letter in s1's letters with any other letter.

Group all strings so that connected strings (directly or transitively) belong to the same group. Each string that connects to no other string forms a group by itself.

Return an array ans of size 2 where:

 - ans[0] is the total number of groups, and

 - ans[1] is the size of the largest group.

Example 1:

Input: words = ["a","b","ab","cde"]
Output: [2,3]
Explanation:
- words[0] can be used to obtain words[1] (by replacing 'a' with 'b'), and words[2] (by adding 'b'). So words[0] is connected to words[1] and words[2].
- words[1] can be used to obtain words[0] (by replacing 'b' with 'a'), and words[2] (by adding 'a'). So words[1] is connected to words[0] and words[2].
- words[2] can be used to obtain words[0] (by deleting 'b'), and words[1] (by deleting 'a'). So words[2] is connected to words[0] and words[1].
- words[3] is not connected to any string in words.
Thus, words can be divided into 2 groups ["a","b","ab"] and ["cde"]. The size of the largest group is 3.

Example 2:

Input: words = ["a","ab","abc"]
Output: [1,3]
Explanation:
- words[0] is connected to words[1].
- words[1] is connected to words[0] and words[2].
- words[2] is connected to words[1].
Since all strings are connected to each other, they should be grouped together.
Thus, the size of the largest group is 3.

Code

1
2
3