> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/similar-string-groups.md).

# Similar String Groups

Two strings `X` and `Y` are similar if we can swap two letters (in different positions) of `X`, so that it equals `Y`. Also two strings `X` and `Y` are similar if they are equal.

For example, `"tars"` and `"rats"` are similar (swapping at positions `0` and `2`), and `"rats"` and `"arts"` are similar, but `"star"` is not similar to `"tars"`, `"rats"`, or `"arts"`.

Together, these form two connected groups by similarity: `{"tars", "rats", "arts"}` and `{"star"}`.  Notice that `"tars"` and `"arts"` are in the same group even though they are not similar.  Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list `A` of strings.  Every string in `A` is an anagram of every other string in `A`.  How many groups are there?

**Example 1:**

```
Input: A = ["tars","rats","arts","star"]
Output: 2
```

**Constraints:**

* `1 <= A.length <= 2000`
* `1 <= A[i].length <= 1000`
* `A.length * A[i].length <= 20000`
* All words in `A` consist of lowercase letters only.
* All words in `A` have the same length and are anagrams of each other.
* The judging time limit has been increased for this question.

```java
class Solution {
    public int numSimilarGroups(String[] A) {
        int[] parent = new int[A.length];
        int[] rank = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            rank[i] = 1;
            parent[i] = i;
        }
        int count = A.length;
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                int diff = 0;
                for (int c = 0; c < A[i].length(); c++)
                    if (A[i].charAt(c) != A[j].charAt(c))
                        diff++;
                if (diff == 0 || diff == 2) {
                    int p1 = findParent(parent, i);
                    int p2 = findParent(parent, j);
                    if (p1 != p2) {
                        if (rank[p1] > rank[p2])
                            parent[p2] = p1;
                        else if (rank[p2] > rank[p1])
                            parent[p1] = p2;
                        else {
                            parent[p1] = p2;
                            rank[p1]++;
                        }
                        count--;
                    }
                }
            }
        }
        return count;
    }

    public int findParent(int[] parent, int node) {
        if (node != parent[node])
            parent[node] = findParent(parent, parent[node]);
        return parent[node];
    }
}
```