##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/839.html

# 839. Similar String Groups (Hard)

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.

Related Topics:
Depth-first Search, Union Find, Graph

## Solution 1. UnionFind

// OJ: https://leetcode.com/problems/similar-string-groups/
// Time: O(NW)
// Space: O(N)
class UnionFind {
vector<int> id;
int size;
public:
UnionFind(int N) : id(N), size(N) {
iota(begin(id), end(id), 0);
}
int find(int x) {
return id[x] == x ? x : (id[x] = find(id[x]));
}
void connect(int x, int y) {
int p = find(x), q = find(y);
if (p == q) return;
id[p] = q;
--size;
}
int getSize() { return size; }
};
class Solution {
bool similar(string &a, string &b) {
int cnt = 0;
for (int i = 0; i < a.size(); ++i) {
if ((cnt += (a[i] != b[i])) > 2) return false;
}
return cnt == 2 || cnt == 0;
}
public:
int numSimilarGroups(vector<string>& A) {
int N = A.size();
UnionFind uf(N);
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (similar(A[i], A[j])) uf.connect(i, j);
}
}
return uf.getSize();
}
};
• class Solution {
public int numSimilarGroups(String[] A) {
Map<String, Integer> stringGroupMap = new HashMap<String, Integer>();
Map<Integer, Set<String>> groupSetMap = new HashMap<Integer, Set<String>>();
int length = A.length;
for (int i = 0; i < length; i++) {
if (stringGroupMap.containsKey(A[i]))
continue;
stringGroupMap.put(A[i], i);
Set<String> set = new HashSet<String>();
groupSetMap.put(i, set);
}
for (int i = 0; i < length; i++) {
String str1 = A[i];
for (int j = i + 1; j < length; j++) {
String str2 = A[j];
if (difference(str1, str2) <= 2) {
int group1 = stringGroupMap.get(str1);
int group2 = stringGroupMap.get(str2);
if (group1 == group2)
continue;
Set<String> set1 = groupSetMap.get(group1);
Set<String> set2 = groupSetMap.get(group2);
if (group1 < group2) {
for (String str : set1)
stringGroupMap.put(str, group1);
groupSetMap.put(group1, set1);
groupSetMap.remove(group2);
} else {
for (String str : set2)
stringGroupMap.put(str, group2);
groupSetMap.put(group2, set2);
groupSetMap.remove(group1);
}
}
}
}
return groupSetMap.size();
}

public int difference(String str1, String str2) {
int difference = 0;
int length = str1.length();
for (int i = 0; i < length; i++) {
if (str1.charAt(i) != str2.charAt(i))
difference++;
}
return difference;
}
}

############

class Solution {
private int[] p;

public int numSimilarGroups(String[] strs) {
int n = strs.length;
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (check(strs[i], strs[j])) {
p[find(i)] = find(j);
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (i == find(i)) {
++ans;
}
}
return ans;
}

private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}

private boolean check(String a, String b) {
int cnt = 0;
for (int i = 0; i < a.length(); ++i) {
if (a.charAt(i) != b.charAt(i)) {
++cnt;
}
}
return cnt <= 2;
}
}

• // OJ: https://leetcode.com/problems/similar-string-groups/
// Time: O(NW)
// Space: O(N)
class UnionFind {
vector<int> id;
int size;
public:
UnionFind(int N) : id(N), size(N) {
iota(begin(id), end(id), 0);
}
int find(int x) {
return id[x] == x ? x : (id[x] = find(id[x]));
}
void connect(int x, int y) {
int p = find(x), q = find(y);
if (p == q) return;
id[p] = q;
--size;
}
int getSize() { return size; }
};
class Solution {
bool similar(string &a, string &b) {
int cnt = 0;
for (int i = 0; i < a.size(); ++i) {
if ((cnt += (a[i] != b[i])) > 2) return false;
}
return cnt == 2 || cnt == 0;
}
public:
int numSimilarGroups(vector<string>& A) {
int N = A.size();
UnionFind uf(N);
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (similar(A[i], A[j])) uf.connect(i, j);
}
}
return uf.getSize();
}
};

• class Solution:
def numSimilarGroups(self, strs: List[str]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]

n, l = len(strs), len(strs[0])
p = list(range(n))
for i in range(n):
for j in range(i + 1, n):
if sum(strs[i][k] != strs[j][k] for k in range(l)) <= 2:
p[find(i)] = find(j)
return sum(i == find(i) for i in range(n))

############

class Solution(object):
def numSimilarGroups(self, strs):
"""
:type strs: List[str]
:rtype: int
"""
N = len(strs)
dsu = DSU(N)
for i in range(N):
for j in range(i + 1, N):
if self.isSimilar(strs[i], strs[j]):
dsu.union(i, j)
return dsu.regions()

def isSimilar(self, str1, str2):
count = 0
for i in range(len(str1)):
if str1[i] != str2[i]:
count += 1
return count == 2 or count == 0

class DSU:
def __init__(self, N):
self.par_ = range(N + 1)
self.regions_ = N

def find(self, x):
if x != self.par_[x]:
self.par_[x] = self.find(self.par_[x])
return self.par_[x]

def union(self, x, y):
px = self.find(x)
py = self.find(y)
if px == py:
return
self.par_[px] = py
self.regions_ -= 1

def regions(self):
return self.regions_

• func numSimilarGroups(strs []string) int {
n := len(strs)
p := make([]int, n)
for i := range p {
p[i] = i
}
check := func(a, b string) bool {
cnt := 0
for i := range a {
if a[i] != b[i] {
cnt++
}
}
return cnt <= 2
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if check(strs[i], strs[j]) {
p[find(i)] = find(j)
}
}
}
ans := 0
for i := 0; i < n; i++ {
if i == find(i) {
ans++
}
}
return ans
}