Similar String Groups solution and explanation
Google
9 more videos on this problem
Similar String Groups | Leetcode - 839 | DFS & BFS | AMAZON | Explanation ➕ Live CodingcodestorywithMIK · 15:10 · 7K views
Similar String Groups | Leetcode - 839 | DSU | AMAZON | Explanation ➕ Live CodingcodestorywithMIK · 11:45 · 4K views
Similar String Groups || DFS || Graphs || Leetcode 839 || C++/Java/PythonAryan Mittal · 12:06 · 4K views
Leetcode 839. Similar String Groups || Google interview questionInterviewDose · 7:24 · 4K views
LeetCode 839. Similar String Groups Explanation and Solutionhappygirlzt · 10:08 · 2K views
Daily Leetcode #1123: Apr 28, 2023 - 839. Similar String GroupsProgramming Live with Larry · 8:02 · 824 views
839. Similar String Groups (Leetcode Hard)Programming Live with Larry · 7:56 · 759 views
839. Similar String Groups | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 17:48 · 671 views
839 || Similar String Groups || C++ || Leetcode Daily ChallengeCodeFreaks · 14:44 · 606 views
LeetCode 839. Similar String Groups | JSer - JavaScript & AlgorithmJSer · 22:57 · 457 views
The problem
Two strings, X and Y, are considered similar if either they are identical or we can make them equivalent by swapping at most two letters (in distinct positions) within the string X.
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 <= 3001 <= strs[i].length <= 300strs[i]consists of lowercase letters only.- All words in
strshave the same length and are anagrams of each other.
Approach overview
Problem Overview: You are given an array of strings where every string is an anagram of the others. Two strings are considered similar if you can swap exactly two characters in one string to make it equal to the other. The task is to count how many groups of similar strings exist.
The key observation: similarity is a transitive relationship. If a is similar to b, and b is similar to c, then all belong to the same group even if a and c are not directly similar. This naturally forms connected components in a graph.
Approach 1: Union-Find (Disjoint Set) (O(n2 * m) time, O(n) space)
Treat each string as a node. Compare every pair of strings and check whether they differ in exactly two positions (or zero). If they are similar, merge their sets using a union-find structure. The similarity check scans characters and records mismatched positions. If the mismatch count exceeds two, stop early. After processing all pairs, the number of unique parents in the disjoint set represents the number of groups. This approach works well because union-find efficiently merges connected components with near-constant amortized operations.
Approach 2: Depth-First Search Graph Traversal (O(n2 * m) time, O(n) space)
Model the problem as an undirected graph where an edge connects two strings if they are similar. Iterate through all string pairs and check similarity. Then run DFS from each unvisited node to mark all reachable nodes in that component. Each DFS traversal corresponds to one similar string group. The similarity check still costs O(m) per pair, so the total complexity becomes O(n^2 * m). This method is conceptually simple and easy to implement if you're comfortable with graph traversal.
Both approaches rely on pairwise comparisons because similarity depends on character positions. The array size n determines how many comparisons happen, while string length m determines the cost of each similarity check.
Recommended for interviews: The Union-Find approach is usually preferred. Interviewers expect you to recognize the connected-components pattern and apply a disjoint-set structure. Explaining the graph interpretation first shows clear reasoning, while implementing union-find demonstrates familiarity with a standard connectivity algorithm used across many array and graph problems.
Approach 1: Union-Find Approach
In this approach, we treat each string as a node in a graph. Two nodes are connected if the corresponding strings are similar. We use a Union-Find data structure to efficiently group the strings into connected components based on similarity.
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
if rootX != rootY:
parent[rootY] = rootX
def are_similar(a, b):
diff = 0
for i in range(len(a)):
if a[i] != b[i]:
diff += 1
if diff > 2:
return False
return diff == 2 or diff == 0
def num_similar_groups(strs):
n = len(strs)
parent = list(range(n))
for i in range(n):
for j in range(i + 1, n):
if are_similar(strs[i], strs[j]):
union(parent, i, j)
return len(set(find(parent, i) for i in range(n)))
# Example usage:
strs = ["tars", "rats", "arts", "star"]
print(num_similar_groups(strs))import java.util.*;
public class Solution {
private int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
private void union(int[] parent, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
parent[rootY] = rootX;
}
private boolean areSimilar(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 diff == 2 || diff == 0;
}
public int numSimilarGroups(String[] strs) {
int n = strs.length;
int[] 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 (areSimilar(strs[i], strs[j])) {
union(parent, i, j);
}
}
}
int count = 0;
for (int i = 0; i < n; i++) {
if (find(parent, i) == i) count++;
}
return count;
}
public static void main(String[] args) {
Solution s = new Solution();
String[] strs = {"tars", "rats", "arts", "star"};
System.out.println(s.numSimilarGroups(strs));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> parent;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union_set(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootY] = rootX;
}
bool areSimilar(string a, string b) {
int diff = 0;
for (int i = 0; i < a.length(); ++i) {
if (a[i] != b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff == 2 || diff == 0;
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
parent.resize(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 (areSimilar(strs[i], strs[j])) {
union_set(i, j);
}
}
}
int count = 0;
for (int i = 0; i < n; ++i) {
if (find(i) == i) {
count++;
}
}
return count;
}
int main() {
vector<string> strs = {"tars", "rats", "arts", "star"};
cout << numSimilarGroups(strs) << endl;
return 0;
}function find(parent, x) {
if (parent[x] !== x) parent[x] = find(parent, parent[x]);
return parent[x];
}
function union(parent, x, y) {
const rootX = find(parent, x);
const rootY = find(parent, y);
if (rootX !== rootY) parent[rootY] = rootX;
}
function areSimilar(a, b) {
let diff = 0;
for (let i = 0; i < a.length; i++) {
if (a[i] !== b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff === 2 || diff === 0;
}
function numSimilarGroups(strs) {
const n = strs.length;
const parent = Array.from({ length: n }, (_, i) => i);
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (areSimilar(strs[i], strs[j])) {
union(parent, i, j);
}
}
}
const groups = new Set();
for (let i = 0; i < n; i++) {
groups.add(find(parent, i));
}
return groups.size;
}
// Example usage:
const strs = ["tars", "rats", "arts", "star"];
console.log(numSimilarGroups(strs));#include <stdio.h>
#include <string.h>
#define MAX 300
int parent[MAX];
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union_set(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootY] = rootX;
}
int areSimilar(char *a, char *b) {
int diff = 0;
for (int i = 0; i < strlen(a); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 2) return 0;
}
}
return diff == 2 || diff == 0;
}
int numSimilarGroups(char **strs, int strsSize) {
for (int i = 0; i < strsSize; i++) parent[i] = i;
for (int i = 0; i < strsSize; i++) {
for (int j = i + 1; j < strsSize; j++) {
if (areSimilar(strs[i], strs[j])) {
union_set(i, j);
}
}
}
int count = 0;
for (int i = 0; i < strsSize; i++) {
if (find(i) == i) {
count++;
}
}
return count;
}using System;
class Solution {
private int Find(int[] parent, int x) {
if (parent[x] != x) parent[x] = Find(parent, parent[x]);
return parent[x];
}
private void Union(int[] parent, int x, int y) {
int rootX = Find(parent, x);
int rootY = Find(parent, y);
if (rootX != rootY) parent[rootY] = rootX;
}
private bool AreSimilar(string a, string b) {
int diff = 0;
for (int i = 0; i < a.Length; i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff == 2 || diff == 0;
}
public int NumSimilarGroups(string[] strs) {
int n = strs.Length;
int[] 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 (AreSimilar(strs[i], strs[j])) {
Union(parent, i, j);
}
}
}
int count = 0;
for (int i = 0; i < n; i++) {
if (Find(parent, i) == i) count++;
}
return count;
}
static void Main() {
Solution s = new Solution();
string[] strs = {"tars", "rats", "arts", "star"};
Console.WriteLine(s.NumSimilarGroups(strs));
}
}The Python implementation involves Union-Find operations for similarity checking and component grouping. The are_similar() function ensures at most two mismatches for a pair of similar strings. Union and path compression make set operations efficient.
Time Complexity: O(n^2 * k) where n is the total number of strings and k is their length.
Space Complexity: O(n) for tracking parents.
Approach 2: Depth-First Search (DFS) Approach
This approach considers each string as a node and treats detecting similarities like exploring components in a graph. We use a depth-first search (DFS) algorithm to explore nodes. If two strings are similar, we explore all strings similar to this pair within a recursive call.
def are_similar(a, b):
diff = 0
for i in range(len(a)):
if a[i] != b[i]:
diff += 1
if diff > 2:
return False
return diff == 2 or diff == 0
def dfs(strs, visited, idx):
visited[idx] = True
for i, s in enumerate(strs):
if not visited[i] and are_similar(strs[idx], s):
dfs(strs, visited, i)
def num_similar_groups(strs):
n = len(strs)
visited = [False] * n
count = 0
for i in range(n):
if not visited[i]:
dfs(strs, visited, i)
count += 1
return count
# Example usage:
strs = ["tars", "rats", "arts", "star"]
print(num_similar_groups(strs))import java.util.*;
public class Solution {
private boolean areSimilar(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 diff == 2 || diff == 0;
}
private void dfs(String[] strs, boolean[] visited, int idx) {
visited[idx] = true;
for (int i = 0; i < strs.length; i++) {
if (!visited[i] && areSimilar(strs[idx], strs[i])) {
dfs(strs, visited, i);
}
}
}
public int numSimilarGroups(String[] strs) {
int n = strs.length;
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(strs, visited, i);
count++;
}
}
return count;
}
public static void main(String[] args) {
Solution s = new Solution();
String[] strs = {"tars", "rats", "arts", "star"};
System.out.println(s.numSimilarGroups(strs));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool areSimilar(string a, string b) {
int diff = 0;
for (int i = 0; i < a.length(); ++i) {
if (a[i] != b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff == 2 || diff == 0;
}
void dfs(vector<string>& strs, vector<bool>& visited, int idx) {
visited[idx] = true;
for (int i = 0; i < strs.size(); ++i) {
if (!visited[i] && areSimilar(strs[idx], strs[i])) {
dfs(strs, visited, i);
}
}
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(strs, visited, i);
count++;
}
}
return count;
}
int main() {
vector<string> strs = {"tars", "rats", "arts", "star"};
cout << numSimilarGroups(strs) << endl;
return 0;
}function areSimilar(a, b) {
let diff = 0;
for (let i = 0; i < a.length; i++) {
if (a[i] !== b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff === 2 || diff === 0;
}
function dfs(strs, visited, idx) {
visited[idx] = true;
for (let i = 0; i < strs.length; i++) {
if (!visited[i] && areSimilar(strs[idx], strs[i])) {
dfs(strs, visited, i);
}
}
}
function numSimilarGroups(strs) {
const n = strs.length;
const visited = Array(n).fill(false);
let count = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
dfs(strs, visited, i);
count++;
}
}
return count;
}
// Example usage:
const strs = ["tars", "rats", "arts", "star"];
console.log(numSimilarGroups(strs));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX 300
bool areSimilar(char* a, char* b) {
int diff = 0;
for (int i = 0; i < strlen(a); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff == 2 || diff == 0;
}
void dfs(char **strs, int idx, int size, bool visited[]) {
visited[idx] = true;
for (int i = 0; i < size; i++) {
if (!visited[i] && areSimilar(strs[idx], strs[i])) {
dfs(strs, i, size, visited);
}
}
}
int numSimilarGroups(char **strs, int strsSize) {
bool visited[MAX] = {false};
int count = 0;
for (int i = 0; i < strsSize; i++) {
if (!visited[i]) {
dfs(strs, i, strsSize, visited);
count++;
}
}
return count;
}
int main() {
char *strs[] = {"tars", "rats", "arts", "star"};
int n = sizeof(strs) / sizeof(strs[0]);
printf("%d\n", numSimilarGroups(strs, n));
return 0;
}using System;
class Solution {
private bool AreSimilar(string a, string b) {
int diff = 0;
for (int i = 0; i < a.Length; i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff == 2 || diff == 0;
}
private void Dfs(string[] strs, bool[] visited, int idx) {
visited[idx] = true;
for (int i = 0; i < strs.Length; i++) {
if (!visited[i] && AreSimilar(strs[idx], strs[i])) {
Dfs(strs, visited, i);
}
}
}
public int NumSimilarGroups(string[] strs) {
int n = strs.Length;
bool[] visited = new bool[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Dfs(strs, visited, i);
count++;
}
}
return count;
}
static void Main() {
Solution s = new Solution();
string[] strs = {"tars", "rats", "arts", "star"};
Console.WriteLine(s.NumSimilarGroups(strs));
}
}Python uses a recursion-based DFS to explore connected nodes starting from any node. The dfs function continually marks all reachable similar strings using a boolean array until complete exploration is achieved, allowing us to count each group accurately.
Time Complexity: O(n^2 * k), where n is the count and k is the string length.
Space Complexity: O(n), for maintaining the list of visited nodes.
Approach 3: Union-Find
We can enumerate any two strings s and t in the list of strings. Since s and t are anagrams, if the number of differing characters at corresponding positions between s and t does not exceed 2, then s and t are similar. We can use the union-find data structure to merge s and t. If the merge is successful, the number of similar string groups decreases by 1.
The final number of similar string groups is the number of connected components in the union-find structure.
Time complexity is O(n^2 times (m + \alpha(n))), and space complexity is O(n). Here, n and m are the length of the list of strings and the length of the strings, respectively, and \alpha(n) is the inverse Ackermann function, which can be considered a very small constant.
class UnionFind {
private p: number[];
private size: number[];
constructor(n: number) {
this.p = Array.from({ length: n }, (_, i) => i);
this.size = Array(n).fill(1);
}
union(a: number, b: number): boolean {
const pa = this.find(a);
const pb = this.find(b);
if (pa === pb) {
return false;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
}
function numSimilarGroups(strs: string[]): number {
const n = strs.length;
const m = strs[0].length;
const uf = new UnionFind(n);
let cnt = n;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
let diff = 0;
for (let k = 0; k < m; ++k) {
if (strs[i][k] !== strs[j][k]) {
diff++;
}
}
if (diff <= 2 && uf.union(i, j)) {
cnt--;
}
}
}
return cnt;
}type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a), uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func numSimilarGroups(strs []string) int {
n := len(strs)
uf := newUnionFind(n)
for i, s := range strs {
for j, t := range strs[:i] {
diff := 0
for k := range s {
if s[k] != t[k] {
diff++
}
}
if diff <= 2 && uf.union(i, j) {
n--
}
}
}
return n
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find Approach | Time Complexity: O(n^2 * k) where n is the total number of strings and k is their length. |
| Depth-First Search (DFS) Approach | Time Complexity: O(n^2 * k), where n is the count and k is the string length. |
| Union-Find | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pairwise Grouping | O(n^2 * m) | O(1) | Conceptual baseline when first analyzing similarity checks |
| Depth-First Search (Graph Components) | O(n^2 * m) | O(n) | When modeling the problem explicitly as a graph traversal |
| Union-Find (Disjoint Set) | O(n^2 * m) | O(n) | Best general solution for counting connected components efficiently |
Frequently asked questions
Is Similar String Groups easy or hard?
Similar String Groups is rated Hard on LeetCode mainly because it requires recognizing the hidden graph structure and applying Union-Find or DFS correctly. The implementation itself is manageable once you identify that the task reduces to counting connected components.
How to solve Similar String Groups in O(n)?
An O(n) solution is not feasible because similarity must be checked between pairs of strings. Determining whether two strings are similar requires scanning their characters, and potentially comparing many pairs. The best achievable complexity for typical constraints is O(n^2 * m).
What is the best approach for Similar String Groups?
The Union-Find (Disjoint Set) approach is the most common solution. Compare every pair of strings and union their sets if they differ in exactly two positions. After processing all pairs, the number of distinct parents represents the number of groups. The overall complexity is O(n^2 * m), where n is the number of strings and m is the string length.
What data structure is used in Similar String Groups?
The most common data structure is Union-Find (Disjoint Set Union) to merge similar strings into groups. Alternatively, you can build a graph and use DFS or BFS to find connected components. Arrays and string comparisons are also used for the similarity check.
What is the time complexity of Similar String Groups?
The optimal time complexity is O(n^2 * m). You must compare every pair of strings (n^2) and each comparison checks characters across the string length m to count mismatches. Both DFS graph traversal and Union-Find solutions share this complexity.
Similar String Groups Python or Java solution approach?
Both Python and Java implementations typically use Union-Find. Iterate through all string pairs, check if they differ in at most two positions, and union their indices if they are similar. Maintain a parent array and count the number of unique roots at the end.
Is Similar String Groups asked at Google, Amazon, or Meta?
Similar String Groups is a graph connectivity problem that appears in interview preparation lists for companies like Google, Amazon, and Meta. It tests recognition of connected components and the ability to apply Union-Find or DFS effectively.