# Similar String Groups
**Difficulty:** HARD
[External](https://leetcode.com/problems/similar-string-groups)
Canonical: https://scaleengineer.com/dsa/problems/similar-string-groups
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## 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 <= 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.

# Approaches
## Graph Construction and Traversal (DFS)
This approach models the problem as a graph problem. Each string in the input list is considered a node in a graph. An edge exists between two nodes if their corresponding strings are "similar". Two strings are similar if they are identical or can be made identical by swapping exactly two characters. The problem then reduces to finding the number of connected components in this graph, as each connected component represents a group of similar strings.
**Time:** O(N^2 * L), where `N` is the number of strings and `L` is the length of each string. The dominant operation is building the graph, which involves `O(N^2)` pairwise comparisons, each taking `O(L)` time. The subsequent DFS takes `O(N + E)` time, where `E` is the number of edges (at most `O(N^2)`), which is subsumed by the graph construction time. · **Space:** O(N^2). The adjacency list can store up to `O(N^2)` edges in the worst case (a fully connected graph). The `visited` array and the recursion stack for DFS require an additional `O(N)` space.
**Pros:** Conceptually straightforward, as it directly models the problem's structure as a graph.; Relatively easy to implement for those familiar with basic graph algorithms.
**Cons:** The space complexity of `O(N^2)` for the adjacency list can be high if the number of strings `N` is large.
### Explanation
The algorithm proceeds in two main phases: graph construction and component counting.

1.  **Graph Construction**: We build an adjacency list representation of the graph. We iterate through every possible pair of strings from the input list `strs`. For each pair `(strs[i], strs[j])`, we check for similarity. A helper function `isSimilar(s1, s2)` determines this by counting the number of positions where the characters differ. Since all strings are anagrams and have the same length, they are similar if this difference count is either 0 (the strings are identical) or 2 (the strings can be made identical with one swap). If they are similar, we add an edge connecting nodes `i` and `j` in our adjacency list.

2.  **Component Counting**: After the graph is built, we count its connected components using a graph traversal algorithm like Depth-First Search (DFS). We use a boolean array `visited` to keep track of nodes that have already been part of a traversal. We also maintain a `groups` counter, initialized to zero. We iterate through all nodes from `0` to `n-1`. If we encounter a node `i` that has not been visited, it means we have found a new, unexplored component. We increment the `groups` counter and launch a DFS from node `i`. The DFS will recursively visit all reachable nodes from `i`, marking them all as visited. This process ensures that every node in a component is visited exactly once.

After the loop finishes, the `groups` counter holds the total number of connected components, which is the number of similar string groups.

```java
public class Solution {
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        if (n <= 1) {
            return n;
        }
        java.util.List<Integer>[] adj = new java.util.ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new java.util.ArrayList<>();
        }

        // Step 1: Build the graph
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isSimilar(strs[i], strs[j])) {
                    adj[i].add(j);
                    adj[j].add(i);
                }
            }
        }

        // Step 2: Count connected components using DFS
        boolean[] visited = new boolean[n];
        int groups = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                groups++;
                dfs(i, adj, visited);
            }
        }
        return groups;
    }

    private void dfs(int u, java.util.List<Integer>[] adj, boolean[] visited) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v, adj, visited);
            }
        }
    }

    private boolean isSimilar(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
        }
        // Similar if identical or can be made equal with one swap.
        return diff == 0 || diff == 2;
    }
}
```
### Algorithm
- Let `N` be the number of strings.
- Create an adjacency list `adj` of size `N`.
- Iterate through all pairs of strings `(strs[i], strs[j])` where `i < j`.
- For each pair, check if they are similar using a helper function `isSimilar`. This function returns true if the strings differ at 0 or 2 positions.
- If `strs[i]` and `strs[j]` are similar, add an edge between `i` and `j` in the adjacency list.
- Initialize a `visited` boolean array of size `N` to `false`.
- Initialize a `groups` counter to 0.
- Iterate from `i = 0` to `N-1`.
- If `visited[i]` is `false`, it means we've found a new group. Increment `groups` and start a DFS traversal from `i`.
- The DFS function marks the current node as visited and recursively calls itself for all unvisited neighbors.
- After the loop, return `groups`.

## Disjoint Set Union (Union-Find)
This approach provides a significant space optimization by using a Disjoint Set Union (DSU) or Union-Find data structure. Instead of explicitly building a graph, we treat each string as an element in a set. We iterate through all pairs of strings, and if two strings are similar, we merge (union) their sets. The total number of groups is the number of disjoint sets remaining at the end.
**Time:** O(N^2 * L), where `N` is the number of strings and `L` is the length of each string. The main loop runs `O(N^2)` times, and each iteration involves an `O(L)` string comparison. The DSU operations are amortized `O(α(N))`, which is practically constant and does not affect the overall complexity. · **Space:** O(N). The DSU data structure requires a `parent` array of size `N`, leading to linear space complexity, which is a significant improvement over the graph-based approach.
**Pros:** Highly space-efficient, with a space complexity of `O(N)`.; The DSU logic is clean and directly models the process of grouping elements.; `find` and `union` operations are nearly constant time on average due to optimizations.
**Cons:** The overall time complexity is still `O(N^2 * L)`, limited by the need to compare all pairs of strings.
### Explanation
The Union-Find data structure is ideal for problems involving partitioning elements into disjoint sets. Here's how it's applied:

1.  **Initialization**: We create a DSU data structure to manage `N` elements, where `N` is the number of strings. Initially, each string is in its own set, so we start with `N` groups. The DSU is typically implemented with a `parent` array, where `parent[i]` stores the parent of element `i`. We also use optimizations like *path compression* and *union by size/rank* to make operations very fast.

2.  **Iterate and Union**: We iterate through all unique pairs of strings `(strs[i], strs[j])`. For each pair, we use the same `isSimilar` helper function to check if they are similar (i.e., differ by 0 or 2 characters).

3.  **Merging Sets**: If `strs[i]` and `strs[j]` are similar, we call the `union(i, j)` operation. This operation finds the representatives (roots) of the sets containing `i` and `j`. If the representatives are different, it means the strings belong to different groups, so we merge them by setting one root as the parent of the other. A successful merge means two groups have combined into one, so we decrement our total group count.

After iterating through all pairs, the final group count in our DSU structure is the answer.

```java
class DSU {
    int[] parent;
    int count; // To store the number of disjoint sets

    public DSU(int n) {
        parent = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // Find with path compression
    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    // Union by rank/size could be added for further optimization, but not strictly necessary here.
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            count--;
        }
    }
}

public class Solution {
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        if (n <= 1) {
            return n;
        }
        DSU dsu = new DSU(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isSimilar(strs[i], strs[j])) {
                    dsu.union(i, j);
                }
            }
        }
        return dsu.count;
    }

    private boolean isSimilar(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
        }
        return diff == 0 || diff == 2;
    }
}
```
### Algorithm
- Let `N` be the number of strings.
- Initialize a DSU data structure with `N` elements. The number of groups is initially `N`.
- Iterate through all pairs of strings `(strs[i], strs[j])` where `i < j`.
- If `isSimilar(strs[i], strs[j])` is true, perform a `union` operation on indices `i` and `j`.
- The `union(i, j)` operation finds the roots of `i` and `j`. If the roots are different, it merges the two sets and decrements the group count.
- After checking all pairs, return the final group count from the DSU structure.

# Solutions
### Java

```java
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 ; } }
```

### Python

```python
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))

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  int numSimilarGroups(vector<string> &strs) {
    int n = strs.size();
    p.resize(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;
  }
  bool check(string a, string b) {
    int cnt = 0;
    for (int i = 0; i < a.size(); ++i)
      if (a[i] != b[i])
        ++cnt;
    return cnt <= 2;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```