## Algorithm

Problem Name: 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`. 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 `strs` of strings where every string in `strs` is an anagram of every other string in `strs`. How many groups are there?

Example 1:

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

Example 2:

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

Constraints:

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

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numSimilarGroups = function (A) {
const all = new Set(A)
const isSimilar = function (w1, w2) {
if (w1 === w2) return true
let misMatch = 0
for (let i = 0; i  <  w1.length; i++) {
if (w1[i] !== w2[i]) misMatch++
if (misMatch > 2) return false
}
return true
}
const recur = function (s) {
all.delete(s)
for (let n of all) {
if (isSimilar(s, n)) {
recur(n)
}
}
}
let ans = 0
while (all.size) {
const current = all.values().next().value
recur(current)
ans++
}
return ans
}
``````
Copy The Code &

Input

cmd
strs = ["tars","rats","arts","star"]

Output

cmd
2

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numSimilarGroups(self, A):
def explore(s):
for v in edges[s]:
if v not in visited: explore(v)
res, edges, visited = 0, {}, set()
if len(A) >= 2 * len(A[0]):
strs = set(A)
for s in A:
if s not in edges: edges[s] = set()
for i in range(len(s) - 1):
for j in range(i + 1, len(s)):
new = s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
if new in strs:
else: edges[new] = {s}
else:
for s in A:
if s not in edges: edges[s] = set()
for t in A:
if s != t:
same = 0
for i, c in enumerate(t):
if c == s[i]: same += 1
if same == len(s) - 2:
else: edges[t] = {s}
for s in A:
if s not in visited:
res += 1
explore(s)
return res
``````
Copy The Code &

Input

cmd
strs = ["tars","rats","arts","star"]

Output

cmd
2