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

For example, "tars"&nbsp;and "rats"&nbsp;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"}.&nbsp; Notice that "tars" and "arts" are in the same group even though they are not similar.&nbsp; 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 strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

&nbsp;
Example 1:

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


Example 2:

Input: strs = ["omv","ovm"]
Output: 1


&nbsp;
Constraints:


	1 &lt;= strs.length &lt;= 300
	1 &lt;= strs[i].length &lt;= 300
	strs[i] consists of lowercase letters only.
	All words in strs have the same length and are anagrams of each other.


class Solution: #839. Similar String Groups
    def numSimilarGroups(self, strs: List[str]) -> int:
        #memo
        visited = set()
        count = 0
        for i in range(len(strs)):
            if i not in visited:
                #dfs
                self.dfs(strs, i, visited)
                #add a new connected area
                count += 1
        return count

    #dfs to search the similar string from 0 to n-1
    def dfs(self, strs, i, visited):
        #add current string to memo
        visited.add(i)
        for j in range(len(strs)):
            if self.isSimilar(strs[i], strs[j]) and j not in visited:
                self.dfs(strs, j , visited)

    # calculate the similarity of two strings
    def isSimilar(self, str1, str2):
        diff_count = 0
        for i in range(len(str1)):
            if str1[i] != str2[i]:
                diff_count += 1
        return diff_count <= 2
class Solution {
    public int numSimilarGroups(String[] strs) {
        boolean[] visited = new boolean[strs.length]; // record the word that we checked
        int res = 0;
        for (int i = 0; i < strs.length; i++) {
            if (!visited[i]) {
                res++;
                dfs(strs, visited, i);
            }
        }
        return res;
    }
    
    void dfs(String[] strs, boolean[] visited, int index) { // explore all similar words we can explore
        visited[index] = true;
        String curr = strs[index];
        for (int i = 0; i < strs.length; i++) {
            if (!visited[i] && isSimilar(curr, strs[i])) {
                dfs(strs, visited, i);
            } 
        }
    }
    
    boolean isSimilar(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
                if (diff > 2) return false;
            }
        }
        return true;
    }
}
class Solution {
public:

    bool similar(string s1,string s2)
    {
        int n=s1.size();
        int i=0,j=n-1;
       int missMatch=0;
        for(i=0;i<n;i++)
        {
            if(s1[i]!=s2[i] and ++missMatch>2)return 0;
        }
        return 1;
    }

    void dfs(string x,unordered_map<string,vector<string>>&adj,unordered_set<string>&visited)
    {
        visited.insert(x);
        for(auto nbr:adj[x])
        {
            if(visited.find(nbr)==visited.end())
            {

                dfs(nbr,adj,visited);
            }
        }
    }

    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        unordered_map<string,vector<string>>adj;
        for(int i=0;i<n;i++)
        {
            string s1 = strs[i];
            for(int j=i+1;j<n;j++)
            {
                string s2 = strs[j];
                if(similar(s1,s2))
                {
                    adj[s1].push_back(s2);
                    adj[s2].push_back(s1);

                }
            }

        }

        int count=0;
        unordered_set<string>visited;
        for(auto x:strs)
        {
            if(visited.find(x)==visited.end())
            {
                //cout<<x<<endl;
                dfs(x,adj,visited);
                count++;
            }
        }
        return count;//(strs[0],strs[2]);

    }
};
var numSimilarGroups = function(strs) {
    const len = strs.length;
    
    // dsu logic
    const dsu = new Array(len).fill(0).map((_, idx) => idx);
    const find = (x) => {
        if(x == dsu[x]) return x;
        return dsu[x] = find(dsu[x]);
    }
    const union = (i, j) => {
        const pi = find(i);
        const pj = find(j);
        if(pi != pj) {
            dsu[pi] = pj;
        }
    }
    
    
    const similar = (a, b) => {
        let c = 0, i = 0, len = a.length;
        while(i < len) {
            if(a[i] != b[i]) c++;
            i++;
            if(c > 2) return false;
        }
        return true;
    }
    
    for(let i = 0; i < len; i++) {
        for(let j = i + 1; j < len; j++) {
            if(similar(strs[i], strs[j])) {
                union(i, j);
            }
        }
    }
    for(let i = 0; i < len; i++) find(i);
    const s = new Set();
    for(let i = 0; i < len; i++) s.add(dsu[i]);
    return s.size;
};
Similar String Groups