1/**
2 * Union-Find (Disjoint Set Union) data structure with path compression and union by size
3 */
4class UnionFind {
5    private final int[] parent;     // parent[i] stores the parent of node i
6    private final int[] size;        // size[i] stores the size of the tree rooted at i
7
8    /**
9     * Initialize Union-Find structure with n elements (0 to n-1)
10     * @param n Number of elements
11     */
12    public UnionFind(int n) {
13        parent = new int[n];
14        size = new int[n];
15      
16        // Initially, each element is its own parent (separate component)
17        for (int i = 0; i < n; ++i) {
18            parent[i] = i;
19            size[i] = 1;
20        }
21    }
22
23    /**
24     * Find the root of the component containing element x
25     * Uses path compression optimization for better performance
26     * @param x Element to find root for
27     * @return Root of the component containing x
28     */
29    public int find(int x) {
30        // Path compression: make every node point directly to root
31        if (parent[x] != x) {
32            parent[x] = find(parent[x]);
33        }
34        return parent[x];
35    }
36
37    /**
38     * Union two components containing elements a and b
39     * Uses union by size optimization (smaller tree attached to larger tree)
40     * @param a First element
41     * @param b Second element
42     * @return true if union was performed (elements were in different components), false otherwise
43     */
44    public boolean union(int a, int b) {
45        int rootA = find(a);
46        int rootB = find(b);
47      
48        // Already in the same component
49        if (rootA == rootB) {
50            return false;
51        }
52      
53        // Union by size: attach smaller tree to larger tree
54        if (size[rootA] > size[rootB]) {
55            parent[rootB] = rootA;
56            size[rootA] += size[rootB];
57        } else {
58            parent[rootA] = rootB;
59            size[rootB] += size[rootA];
60        }
61      
62        return true;
63    }
64}
65
66/**
67 * Solution for finding number of similar string groups
68 * Two strings are similar if they differ by exactly 0 or 2 characters (can be made equal by swapping)
69 */
70class Solution {
71    /**
72     * Find the number of groups of similar strings
73     * @param strs Array of strings (all anagrams of each other)
74     * @return Number of groups where strings in same group are similar
75     */
76    public int numSimilarGroups(String[] strs) {
77        int n = strs.length;          // Number of strings
78        int m = strs[0].length();     // Length of each string
79      
80        // Initialize Union-Find with n strings (indexed 0 to n-1)
81        UnionFind unionFind = new UnionFind(n);
82      
83        // Start with n groups (each string is its own group)
84        int groupCount = n;
85      
86        // Check all pairs of strings
87        for (int i = 0; i < n; ++i) {
88            for (int j = 0; j < i; ++j) {
89                // Count character differences between strings i and j
90                int differenceCount = 0;
91                for (int k = 0; k < m; ++k) {
92                    if (strs[i].charAt(k) != strs[j].charAt(k)) {
93                        ++differenceCount;
94                    }
95                }
96              
97                // If strings are similar (differ by 0 or 2 characters)
98                // and successfully united (were in different groups)
99                if (differenceCount <= 2 && unionFind.union(i, j)) {
100                    // Decrease group count as two groups merged into one
101                    --groupCount;
102                }
103            }
104        }
105      
106        return groupCount;
107    }
108}
109

1class UnionFind {
2public:
3    /**
4     * Constructor: Initialize Union-Find data structure with n elements
5     * @param n: Number of elements (0 to n-1)
6     */
7    UnionFind(int n) {
8        parent = vector<int>(n);
9        rank = vector<int>(n, 1);
10        // Initialize each element as its own parent (self-loop)
11        iota(parent.begin(), parent.end(), 0);
12    }
13
14    /**
15     * Unite two elements into the same set
16     * @param a: First element
17     * @param b: Second element
18     * @return: true if union was performed (elements were in different sets), false otherwise
19     */
20    bool unite(int a, int b) {
21        int rootA = find(a);
22        int rootB = find(b);
23      
24        // Already in the same set
25        if (rootA == rootB) {
26            return false;
27        }
28      
29        // Union by rank: attach smaller tree under root of larger tree
30        if (rank[rootA] > rank[rootB]) {
31            parent[rootB] = rootA;
32            rank[rootA] += rank[rootB];
33        } else {
34            parent[rootA] = rootB;
35            rank[rootB] += rank[rootA];
36        }
37      
38        return true;
39    }
40
41    /**
42     * Find the root/representative of the set containing element x
43     * Uses path compression for optimization
44     * @param x: Element to find root for
45     * @return: Root element of the set containing x
46     */
47    int find(int x) {
48        // Path compression: make every node point directly to root
49        if (parent[x] != x) {
50            parent[x] = find(parent[x]);
51        }
52        return parent[x];
53    }
54
55private:
56    vector<int> parent;  // Parent array for Union-Find
57    vector<int> rank;    // Rank/size array for union by rank optimization
58};
59
60class Solution {
61public:
62    /**
63     * Find number of groups of similar strings
64     * Two strings are similar if they differ by at most 2 characters
65     * @param strs: Vector of strings to group
66     * @return: Number of similar groups
67     */
68    int numSimilarGroups(vector<string>& strs) {
69        int numStrings = strs.size();
70        int stringLength = strs[0].size();
71      
72        // Initially, each string is its own group
73        int numGroups = numStrings;
74      
75        UnionFind uf(numStrings);
76      
77        // Check all pairs of strings
78        for (int i = 0; i < numStrings; ++i) {
79            for (int j = 0; j < i; ++j) {
80                // Count number of differing characters between strs[i] and strs[j]
81                int diffCount = 0;
82                for (int k = 0; k < stringLength; ++k) {
83                    if (strs[i][k] != strs[j][k]) {
84                        diffCount++;
85                    }
86                }
87              
88                // If strings are similar (differ by at most 2 chars) and not already in same group
89                if (diffCount <= 2 && uf.unite(i, j)) {
90                    // Successfully merged two groups, decrease group count
91                    numGroups--;
92                }
93            }
94        }
95      
96        return numGroups;
97    }
98};
99

1// Parent array for Union-Find structure
2let parent: number[];
3// Size array for union by rank optimization
4let size: number[];
5
6/**
7 * Initializes the Union-Find data structure
8 * @param n - Number of elements
9 */
10function initUnionFind(n: number): void {
11    // Initialize each element as its own parent (self-loop)
12    parent = Array.from({ length: n }, (_, index) => index);
13    // Initialize size of each component as 1
14    size = Array(n).fill(1);
15}
16
17/**
18 * Unites two elements into the same set
19 * @param a - First element
20 * @param b - Second element
21 * @returns true if union was performed, false if already in same set
22 */
23function union(a: number, b: number): boolean {
24    // Find root parents of both elements
25    const rootA = find(a);
26    const rootB = find(b);
27  
28    // If already in the same set, no union needed
29    if (rootA === rootB) {
30        return false;
31    }
32  
33    // Union by rank: attach smaller tree under larger tree
34    if (size[rootA] > size[rootB]) {
35        parent[rootB] = rootA;
36        size[rootA] += size[rootB];
37    } else {
38        parent[rootA] = rootB;
39        size[rootB] += size[rootA];
40    }
41  
42    return true;
43}
44
45/**
46 * Finds the root parent of an element with path compression
47 * @param x - Element to find root for
48 * @returns Root parent of the element
49 */
50function find(x: number): number {
51    // Path compression: make all nodes point directly to root
52    if (parent[x] !== x) {
53        parent[x] = find(parent[x]);
54    }
55    return parent[x];
56}
57
58/**
59 * Counts the number of similar string groups
60 * Two strings are similar if they differ by at most 2 characters
61 * @param strs - Array of strings to group
62 * @returns Number of distinct groups
63 */
64function numSimilarGroups(strs: string[]): number {
65    const n = strs.length;
66    const stringLength = strs[0].length;
67  
68    // Initialize Union-Find structure
69    initUnionFind(n);
70  
71    // Start with n groups (each string is its own group)
72    let groupCount = n;
73  
74    // Compare all pairs of strings
75    for (let i = 0; i < n; i++) {
76        for (let j = 0; j < i; j++) {
77            // Count character differences between strings
78            let differenceCount = 0;
79            for (let charIndex = 0; charIndex < stringLength; charIndex++) {
80                if (strs[i][charIndex] !== strs[j][charIndex]) {
81                    differenceCount++;
82                }
83            }
84          
85            // If strings are similar (differ by at most 2 chars) and not yet connected
86            if (differenceCount <= 2 && union(i, j)) {
87                // Decrease group count when two groups merge
88                groupCount--;
89            }
90        }
91    }
92  
93    return groupCount;
94}
95