字符串分组

import java.util.*;
import java.util.stream.*;

// 思路：使用并查集（Union-Find）结合Java Stream API来解决分组问题。首先初始化每个字符串的唯一ID，然后通过遍历字符串，将关联的字符串合并在同一个组中。最后统计每个组的大小，并找到最大的组大小。
public class Solution {
    public int[] groupStrings(String[] words) {
        int n = words.length;
        UnionFind uf = new UnionFind(n);
        Map<String, Integer> map = new HashMap<>();
        IntStream.range(0, n).forEach(i -> {
            char[] arr = words[i].toCharArray();
            Arrays.sort(arr);
            String sorted = new String(arr);
            if (!map.containsKey(sorted)) {
                map.put(sorted, i);
            } else {
                uf.union(i, map.get(sorted));
            }
            IntStream.range(0, arr.length).forEach(j -> {
                char temp = arr[j];
                arr[j] = '#'; // 替换一个字母
                String modified = new String(arr);
                if (map.containsKey(modified)) {
                    uf.union(i, map.get(modified));
                }
                arr[j] = temp; // 复原字母
            });
        });
        int[] count = new int[n];
        IntStream.range(0, n).forEach(i -> count[uf.find(i)]++);
        int groups = (int) IntStream.of(count).filter(size -> size > 0).count();
        int maxSize = IntStream.of(count).max().orElse(0);
        return new int[]{groups, maxSize};
    }

    class UnionFind {
        int[] parent, rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            IntStream.range(0, n).forEach(i -> parent[i] = i);
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }
}