Similar String Groups
Problem
Two strings are similar if they are equal or differ by exactly one swap of two characters. Given a list of anagrams, return the number of similar-groups (connected components under this relation).
strs = ["tars","rats","arts","star"]2def numSimilarGroups(strs):
n = len(strs)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def similar(a, b):
diff = [i for i in range(len(a)) if a[i] != b[i]]
return len(diff) == 0 or (len(diff) == 2 and a[diff[0]] == b[diff[1]] and a[diff[1]] == b[diff[0]])
for i in range(n):
for j in range(i + 1, n):
if similar(strs[i], strs[j]):
parent[find(i)] = find(j)
return sum(1 for i in range(n) if find(i) == i)
function numSimilarGroups(strs) {
const n = strs.length;
const parent = Array.from({length: n}, (_, i) => i);
const find = x => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
const similar = (a, b) => {
let diff = 0, p = -1, q = -1;
for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) {
diff++; if (diff > 2) return false;
if (p === -1) p = i; else q = i;
}
return diff === 0 || (diff === 2 && a[p] === b[q] && a[q] === b[p]);
};
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) {
if (similar(strs[i], strs[j])) parent[find(i)] = find(j);
}
let groups = 0;
for (let i = 0; i < n; i++) if (find(i) === i) groups++;
return groups;
}
class Solution {
int[] parent;
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
boolean similar(String a, String b) {
int diff = 0, p = -1, q = -1;
for (int i = 0; i < a.length(); i++) if (a.charAt(i) != b.charAt(i)) {
diff++; if (diff > 2) return false;
if (p == -1) p = i; else q = i;
}
return diff == 0 || (diff == 2 && a.charAt(p) == b.charAt(q) && a.charAt(q) == b.charAt(p));
}
public int numSimilarGroups(String[] strs) {
int n = strs.length;
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
if (similar(strs[i], strs[j])) parent[find(i)] = find(j);
int groups = 0;
for (int i = 0; i < n; i++) if (find(i) == i) groups++;
return groups;
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> parent;
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
bool similar(const string &a, const string &b) {
int diff = 0, p = -1, q = -1;
for (int i = 0; i < (int)a.size(); i++) if (a[i] != b[i]) {
diff++; if (diff > 2) return false;
if (p == -1) p = i; else q = i;
}
return diff == 0 || (diff == 2 && a[p] == b[q] && a[q] == b[p]);
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
parent.resize(n); iota(parent.begin(), parent.end(), 0);
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
if (similar(strs[i], strs[j])) parent[find(i)] = find(j);
int groups = 0;
for (int i = 0; i < n; i++) if (find(i) == i) groups++;
return groups;
}
};
Explanation
We want to count how many clusters of strings are connected, where two strings link up if they are equal or differ by exactly one swap. This is a classic grouping problem, and a great fit for union-find (also called disjoint set union).
The core idea: give every string its own group at the start, then for each pair check if they are similar; if they are, merge their groups. At the end, the number of distinct groups is the answer.
Two strings are similar when the positions where they differ number either 0 (already equal) or exactly 2, and at those two positions the characters are swapped versions of each other. The helper similar(a, b) checks exactly that.
Union-find tracks a parent for each string. find(i) follows parents up to the group's root, and parent[find(i)] = find(j) joins two groups. Counting how many strings are their own root (find(i) == i) gives the number of groups.
Example: ["tars","rats","arts","star"]. tars and rats swap to each other, so they merge; arts joins too. star stays alone. That leaves 2 groups.