Groups of Strings

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

from typing import List

class Solution:
    def groupStrings(self, words: List[str]) -> List[int]:
        def find(ds, i):
            return i if ds[i] < 0 else find(ds, ds[i])

        def merge(ds, i, mask):
            if mask in m:
                pi = find(ds, i)
                pj = find(ds, m[mask])
                if pi != pj:
                    if ds[pi] > ds[pj]:
                        pi, pj = pj, pi
                    ds[pi] += ds[pj]
                    ds[pj] = pi
            else:
                m[mask] = i

        ds = [-1] * len(words)
        m = {}
        for i in range(len(words)):
            mask = 0
            for ch in words[i]:
                mask |= 1 << (ord(ch) - ord('a'))
            merge(ds, i, mask)
            for j in range(26):
                if mask & (1 << j):
                    merge(ds, i, mask ^ (1 << j))

        return [sum(1 for i in ds if i < 0), -min(ds)]