Similar String Groups

Hard

#0793Time: 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.1 company

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Array Hash Table String

Companies

DoorDash

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The algorithm proceeds in two main phases: graph construction and component counting.

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.
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.

1public class Solution {2    public int numSimilarGroups(String[] strs) {3        int n = strs.length;4        if (n <= 1) {5            return n;6        }7        java.util.List<Integer>[] adj = new java.util.ArrayList[n];8        for (int i = 0; i < n; i++) {9            adj[i] = new java.util.ArrayList<>();10        }11 12        // Step 1: Build the graph13        for (int i = 0; i < n; i++) {14            for (int j = i + 1; j < n; j++) {15                if (isSimilar(strs[i], strs[j])) {16                    adj[i].add(j);17                    adj[j].add(i);18                }19            }20        }21 22        // Step 2: Count connected components using DFS23        boolean[] visited = new boolean[n];24        int groups = 0;25        for (int i = 0; i < n; i++) {26            if (!visited[i]) {27                groups++;28                dfs(i, adj, visited);29            }30        }31        return groups;32    }33 34    private void dfs(int u, java.util.List<Integer>[] adj, boolean[] visited) {35        visited[u] = true;36        for (int v : adj[u]) {37            if (!visited[v]) {38                dfs(v, adj, visited);39            }40        }41    }42 43    private boolean isSimilar(String s1, String s2) {44        int diff = 0;45        for (int i = 0; i < s1.length(); i++) {46            if (s1.charAt(i) != s2.charAt(i)) {47                diff++;48            }49        }50        // Similar if identical or can be made equal with one swap.51        return diff == 0 || diff == 2;52    }53}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

The Union-Find data structure is ideal for problems involving partitioning elements into disjoint sets. Here's how it's applied:

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.
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).
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.

1class DSU {2    int[] parent;3    int count; // To store the number of disjoint sets4 5    public DSU(int n) {6        parent = new int[n];7        count = n;8        for (int i = 0; i < n; i++) {9            parent[i] = i;10        }11    }12 13    // Find with path compression14    public int find(int i) {15        if (parent[i] == i) {16            return i;17        }18        return parent[i] = find(parent[i]);19    }20 21    // Union by rank/size could be added for further optimization, but not strictly necessary here.22    public void union(int i, int j) {23        int rootI = find(i);24        int rootJ = find(j);25        if (rootI != rootJ) {26            parent[rootI] = rootJ;27            count--;28        }29    }30}31 32public class Solution {33    public int numSimilarGroups(String[] strs) {34        int n = strs.length;35        if (n <= 1) {36            return n;37        }38        DSU dsu = new DSU(n);39 40        for (int i = 0; i < n; i++) {41            for (int j = i + 1; j < n; j++) {42                if (isSimilar(strs[i], strs[j])) {43                    dsu.union(i, j);44                }45            }46        }47        return dsu.count;48    }49 50    private boolean isSimilar(String s1, String s2) {51        int diff = 0;52        for (int i = 0; i < s1.length(); i++) {53            if (s1.charAt(i) != s2.charAt(i)) {54                diff++;55            }56        }57        return diff == 0 || diff == 2;58    }59}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class Solution:2    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))

1class Solution {2public:3  vector<int> p;4  int numSimilarGroups(vector<string> &strs) {5    int n = strs.size();6    p.resize(n);7    for (int i = 0; i < n; ++i)8      p[i] = i;9    for (int i = 0; i < n; ++i)10      for (int j = i + 1; j < n; ++j)11        if (check(strs[i], strs[j]))12          p[find(i)] = find(j);13    int ans = 0;14    for (int i = 0; i < n; ++i)15      if (i == find(i))16        ++ans;17    return ans;18  }19  bool check(string a, string b) {20    int cnt = 0;21    for (int i = 0; i < a.size(); ++i)22      if (a[i] != b[i])23        ++cnt;24    return cnt <= 2;25  }26  int find(int x) {27    if (p[x] != x)28      p[x] = find(p[x]);29    return p[x];30  }31};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem