给你一个下标从 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]中每个字母最多只出现一次。
class Solution:
def groupStrings(self, words: List[str]) -> List[int]:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
nonlocal mx, n
if b not in p:
return
pa, pb = find(a), find(b)
if pa == pb:
return
p[pa] = pb
size[pb] += size[pa]
mx = max(mx, size[pb])
n -= 1
p = {}
size = Counter()
n = len(words)
mx = 0
for word in words:
x = 0
for c in word:
x |= 1 << (ord(c) - ord('a'))
p[x] = x
size[x] += 1
mx = max(mx, size[x])
if size[x] > 1:
n -= 1
for x in p.keys():
for i in range(26):
union(x, x ^ (1 << i))
if (x >> i) & 1:
for j in range(26):
if ((x >> j) & 1) == 0:
union(x, x ^ (1 << i) | (1 << j))
return [n, mx]class Solution {
private Map<Integer, Integer> p;
private Map<Integer, Integer> size;
private int mx;
private int n;
public int[] groupStrings(String[] words) {
p = new HashMap<>();
size = new HashMap<>();
n = words.length;
mx = 0;
for (String word : words) {
int x = 0;
for (char c : word.toCharArray()) {
x |= 1 << (c - 'a');
}
p.put(x, x);
size.put(x, size.getOrDefault(x, 0) + 1);
mx = Math.max(mx, size.get(x));
if (size.get(x) > 1) {
--n;
}
}
for (int x : p.keySet()) {
for (int i = 0; i < 26; ++i) {
union(x, x ^ (1 << i));
if (((x >> i) & 1) != 0) {
for (int j = 0; j < 26; ++j) {
if (((x >> j) & 1) == 0) {
union(x, x ^ (1 << i) | (1 << j));
}
}
}
}
}
return new int[] {n, mx};
}
private int find(int x) {
if (p.get(x) != x) {
p.put(x, find(p.get(x)));
}
return p.get(x);
}
private void union(int a, int b) {
if (!p.containsKey(b)) {
return;
}
int pa = find(a), pb = find(b);
if (pa == pb) {
return;
}
p.put(pa, pb);
size.put(pb, size.get(pb) + size.get(pa));
mx = Math.max(mx, size.get(pb));
--n;
}
}class Solution {
public:
int mx, n;
vector<int> groupStrings(vector<string>& words) {
unordered_map<int, int> p;
unordered_map<int, int> size;
mx = 0;
n = words.size();
for (auto& word : words) {
int x = 0;
for (auto& c : word) x |= 1 << (c - 'a');
p[x] = x;
++size[x];
mx = max(mx, size[x]);
if (size[x] > 1) --n;
}
for (auto& [x, _] : p) {
for (int i = 0; i < 26; ++i) {
unite(x, x ^ (1 << i), p, size);
if ((x >> i) & 1) {
for (int j = 0; j < 26; ++j) {
if (((x >> j) & 1) == 0) unite(x, x ^ (1 << i) | (1 << j), p, size);
}
}
}
}
return {n, mx};
}
int find(int x, unordered_map<int, int>& p) {
if (p[x] != x) p[x] = find(p[x], p);
return p[x];
}
void unite(int a, int b, unordered_map<int, int>& p, unordered_map<int, int>& size) {
if (!p.count(b)) return;
int pa = find(a, p), pb = find(b, p);
if (pa == pb) return;
p[pa] = pb;
size[pb] += size[pa];
mx = max(mx, size[pb]);
--n;
}
};func groupStrings(words []string) []int {
p := map[int]int{}
size := map[int]int{}
mx, n := 0, len(words)
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
union := func(a, b int) {
if _, ok := p[b]; !ok {
return
}
pa, pb := find(a), find(b)
if pa == pb {
return
}
p[pa] = pb
size[pb] += size[pa]
mx = max(mx, size[pb])
n--
}
for _, word := range words {
x := 0
for _, c := range word {
x |= 1 << (c - 'a')
}
p[x] = x
size[x]++
mx = max(mx, size[x])
if size[x] > 1 {
n--
}
}
for x := range p {
for i := 0; i < 26; i++ {
union(x, x^(1<<i))
if ((x >> i) & 1) != 0 {
for j := 0; j < 26; j++ {
if ((x >> j) & 1) == 0 {
union(x, x^(1<<i)|(1<<j))
}
}
}
}
}
return []int{n, mx}
}