title
给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。
如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：
- 往
s1的字母集合中添加一个字母。 - 从
s1的字母集合中删去一个字母。 - 将
s1中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。
数组 words 可以分为一个或者多个无交集的 组 。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组。
注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。
请你返回一个长度为 2 的数组 ans ：
ans[0]是words分组后的 总组数 。ans[1]是字符串数目最多的组所包含的字符串数目。
示例 1：
输入：words = ["a","b","ab","cde"]
输出：[2,3]
解释：
- words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。所以 words[0] 与 words[1] 和 words[2] 关联。
- words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。所以 words[1] 与 words[0] 和 words[2] 关联。
- words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 关联。
- words[3] 与 words 中其他字符串都不关联。
所以，words 可以分成 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。
示例 2：
输入：words = ["a","ab","abc"]
输出：[1,3]
解释：
- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。
所以最大的组大小为 3 。
提示：
1 <= words.length <= 2 * 1041 <= words[i].length <= 26words[i]只包含小写英文字母。words[i]中每个字母最多只出现一次。
solution
word通过转换，就属于一组。这里转换实现是通过位运算来的。
然后求组的数量 和最大组的元素数量，注意可能一个word出现多次，所以要累计cnt。
实现上通过并查集，其实也可以通过bfs求连通分量，是一样的。
class UnionFind:
def __init__(self):
self.parent = {}
def union(self, a: int, b: int):
ra = self.find(a)
rb = self.find(b)
self.parent[ra] = rb
def find(self, a: int) -> int:
if a not in self.parent:
self.parent[a] = a
if self.parent[a] == a:
return a
ra = self.find(self.parent[a])
self.parent[a] = ra
return ra
def is_connected(self, a, b):
return self.find(a) == self.find(b)
class Solution:
def groupStrings(self, words: List[str]) -> List[int]:
uf = UnionFind()
nums = {}
for w in words:
x = 0
for p in w:
x |= 1 << (ord(p) - ord('a'))
nums[x] = nums.get(x, 0) + 1
for k in nums:
x = k
for i in range(26):
x1 = x ^ (1 << i)
if x1 in nums:
uf.union(x, x1)
if x & (1 << i):
for j in range(26):
if x & (1 << j) == 0:
x2 = (x ^ (1 << i)) | (1 << j)
if x2 in nums:
uf.union(x, x2)
res = collections.Counter()
for k, v in nums.items():
res[uf.find(k)] += v
return [len(res.keys()), res.most_common(1)[0][1]]