> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/839.-similar-string-groups.md).

# 839. 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`.

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.

```cpp
bool isSimilar(const string& s1, const string& s2) {
    for (int i = 0, cnt = 0; i < s1.length(); ++i) {
        if (s1[i] == s2[i]) continue;
        if (++cnt > 2) return false;
    }
    return true;
}
// Find
int getRoot(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = getRoot(roots, roots[i]);
}
// Union Find Solution
int numSimilarGroups(vector<string>& A) {
    int n = A.size(), res = n;
    vector<int> roots(n);
    for (int i = 0; i < n; ++i) roots[i] = i;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (!isSimilar(A[i], A[j])) continue;
            int r_i = getRoot(roots, i), r_j = getRoot(roots, j);
            if (r_i == r_j) continue;
            // Union
            roots[r_j] = r_i;
            --res;
        }
    }
    return res;
}
```

```cpp
// DFS
bool isSimilar(const string& s1, const string& s2) {
    for (int i = 0, cnt = 0; i < s1.length(); ++i) {
        if (s1[i] == s2[i]) continue;
        if (++cnt > 2) return false;
    }
    return true;
}
void helper(const vector<string>& A, unordered_set<string>& visited, const string& str) {
    if (visited.count(str)) return;
    visited.insert(str);
    for (const string& word : A) {
        if (isSimilar(str, word)) {
            helper(A, visited, word);
        }
    }
}
int numSimilarGroups(vector<string>& A) { // time: O(n^2); space: O(n)
    int n = A.size(), res = 0;
    unordered_set<string> visited;
    for (const string& s : A) {
        if (visited.count(s)) continue;
        ++res;
        helper(A, visited, s);
    }
    return res;
}
```

```cpp
// BFS
int numSimilarGroups(vector<string>& A) { // time: O(n^2); space: O(n)
    int n = A.size(), res = 0;
    vector<bool> visited(n, false);
    queue<string> q;
    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        ++res;
        q.push(A[i]);
        while (!q.empty()) {
            string t = q.front(); q.pop();
            for (int j = 0; j < n; ++j) {
                if (visited[j]) continue;
                int diff = 0;
                for (int k = 0; k < A[j].length(); ++k) {
                    if (t[k] == A[j][k]) continue;
                    if (++diff > 2) break;
                }
                if (diff == 0 || diff == 2) {
                    if (diff == 2) q.push(A[j]);
                    visited[j] = true;
                }
            }
        }
    }
    return res;
}
```