839. Similar String Groups
Problem Description
The problem requires us to determine the number of groups of similar strings within a list called strs. Two strings are considered similar if they can be made identical by swapping at most two letters in distinct positions within one of the strings. A group of similar strings is defined such that any string belongs to the group if it is similar to at least one other string in the group. Unlike simple string matching, two strings could be in the same group without being directly similar if they are connected through a chain of similarities. This forms a kind of "similarity network". The task is to count how many such networks or groups are present in the given list of strings.
A key factor to note is that every string in strs is an anagram of every other string in strs, which means they all contain the same characters but in different orders.
Intuition
To solve this problem, we can use a graph-based approach, treating each string as a node and connecting nodes if the strings are similar (considering the condition of being able to swap at most two letters). Effectively, each connected component in the graph would represent a group of similar strings. We can then count how many connected components exist in the graph to answer the question.
The solution uses the Union-Find data structure, which is a very efficient way to track and merge connected components. Each node (string) initially represents a separate group (its own parent). As we iterate over pairs of strings and find that they are similar, we unify them by assigning them to the same group (or in Union-Find terms, making one of them's root parent the parent of the other). The find function is used to determine the root parent of a node, and it recursively updates each node's parent to be the top-most parent, thereby flattening the structure and speeding up future queries. We respect the rule that two strings are considered similar if they have two or less mismatched characters positions since all strings are anagrams of one another.
As we proceed with the unification process for every similar pair of strings, the number of groups gets reduced until all similar strings are connected. Once we have processed all strings, the number of groups is the count of strings that are their own parent, which indicates that they are the root of their respective groups.
The essence of the solution is in identifying these connected components using the similarity rule provided, and efficiently keeping track of and merging these components with Union-Find.
Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.
Which of the following shows the order of node visit in a Breadth-first Search?
Solution Approach
The solution to this problem implements the Union-Find data structure, which is key to solving many problems that involve the grouping or partitioning of elements into disjoint sets. The basic operations of Union-Find are find, which gets the representative of a set (in this case, the index of a string that serves as the root parent), and union, which combines two sets into one (achieved by linking the parent of one set to the other).
Here's a step-by-step explanation of how the provided code works:
-
Initialization: Each string is assigned its own group initially. This is represented in the code as a list
pwhere each element is initialized to its own index, meaning it is its own parent:1p = list(range(n)) -
Find Function: A recursive
findfunction is used to look for the root parent of a string. Along the way, it performs path compression by directly connecting the nodes to their root parent, which speeds up subsequentfindoperations:1def find(x): 2 if p[x] != x: 3 p[x] = find(p[x]) 4 return p[x] -
Iterating Over String Pairs: The main logic iterates over all pairs of strings and counts the differences in their characters. If there are at most two differences (swaps), it means that the strings are similar:
1for i in range(n): 2 for j in range(i + 1, n): 3 if sum(strs[i][k] != strs[j][k] for k in range(l)) <= 2: -
Union Operation: When two strings are found to be similar, their groups are unified by setting the parent of one's group to be the parent of the other's group. This effectively merges their sets:
1p[find(i)] = find(j) -
Counting Groups: After all pairs have been considered, the number of groups is the count of strings that are still their own parent, which are the roots of the disjoint sets:
1return sum(i == find(i) for i in range(n))
In essence, the code uses Union-Find with path compression to group the similar strings efficiently. It all comes down to iterative comparisons of strings and updating the data structure to reflect these relationships, which allows us to count the separate groups without needing to explicitly maintain or search the graph of connected components.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Example Walkthrough
Let's use a small example to illustrate the solution approach described above. Suppose our list of strings strs is as follows:
1strs = ["tars", "rats", "arts", "star"]
Each string in strs is an anagram of every other string, containing the same characters in different orders.
Step 1: Initialization
We start by initializing the parent list p with the indices of the strings, assuming each string is its own group:
1p = [0, 1, 2, 3]
Step 2: Find Function
We define our find function, which will help us find the root parent of a string and apply path compression:
1def find(x):
2 if p[x] != x:
3 p[x] = find(p[x])
4 return p[x]
Step 3: Iterating Over String Pairs
Next, we compare each pair of strings to see if they are similar, which means there can be at most two character swaps to make them identical:
- Comparing "tars" and "rats": There is one swap difference (
t-randr-t), so they are similar. - Comparing "tars" and "arts": There are two swap differences (
t-aanda-t), so they are similar. - No need to compare "tars" and "star" since "tars" has already been compared to "rats" and "arts", which share the same set of characters.
- Comparing "rats" and "arts": There is one swap difference (
r-aanda-r), so they are similar. - No need to compare "rats" and "star" since "rats" has already been shown to be part of a group with "tars" and "arts", and "star" shares the same set of characters. They are all similar by association.
- No need to compare "arts" and "star" as they are already part of the same similarity group.
Step 4: Union Operation
When we find pairs that are similar, we perform the union by setting the parent of one to the root parent of the other:
- For "tars" and "rats" we do
p[find(0)] = find(1), which makes them part of the same group. - For "tars" and "arts" we do
p[find(0)] = find(2), but since "tars" and "rats" are already connected, this groups "arts" with them. - For "rats" and "arts" we do
p[find(1)] = find(2), but all three are already connected, so no changes are needed.
After these operations, p might look like [1, 1, 1, 3] indicating that "tars", "rats", and "arts" have a common root which is the index of "rats".
Step 5: Counting Groups
To count the number of groups, we count how many strings are their own parent:
1return sum(i == find(i) for i in range(4))
Since "star" hasn't been merged with any other string, it remains its own parent. Therefore, the count of groups is 2, representing the two sets, one with "tars", "rats", and "arts", and the separate one with "star".
In summary, using the provided strings as inputs for the implementation of the Union-Find based algorithm, we could identify and count the separate similarity groups within the list by analyzing the string pairs and applying the union operations accordingly.
Solution Implementation
1class Solution:
2 def numSimilarGroups(self, strs: List[str]) -> int:
3 def find_leader(member):
4 # Recursively find the leader for the current member
5 # and perform path compression along the way.
6 if parent[member] != member:
7 parent[member] = find_leader(parent[member])
8 return parent[member]
9
10 # Get the total number of strings and the length of each string.
11 num_strings = len(strs)
12 length_of_strings = len(strs[0])
13
14 # Initialize the parent array for union-find structure.
15 parent = list(range(num_strings))
16
17 # Compare every pair of strings in the array.
18 for i in range(num_strings):
19 for j in range(i + 1, num_strings):
20 # Count the differences between two strings and
21 # connect them if they have at most 2 differences.
22 if sum(strs[i][k] != strs[j][k] for k in range(length_of_strings)) <= 2:
23 # Union of the sets that contain i and j
24 # by assigning the leader of iโs set to the leader of j's set.
25 parent[find_leader(i)] = find_leader(j)
26
27 # Count the number of unique sets by checking the number of nodes
28 # that are their own leader.
29 return sum(i == find_leader(i) for i in range(num_strings))
301class Solution {
2 private int[] parent; // Array representing the parent of each element in the disjoint-set
3
4 // Method to find the number of similarity groups in the input strings
5 public int numSimilarGroups(String[] strs) {
6 int n = strs.length; // Number of strings in the array
7 parent = new int[n]; // Initialize the parent array for disjoint-set
8
9 // Initialize each string to be its own parent (self loop)
10 for (int i = 0; i < n; ++i) {
11 parent[i] = i;
12 }
13
14 // Compare each string with every other string to check for similarity
15 for (int i = 0; i < n; ++i) {
16 for (int j = i + 1; j < n; ++j) {
17 if (isSimilar(strs[i], strs[j])) {
18 // If strings are similar, union their sets
19 parent[findParent(i)] = findParent(j);
20 }
21 }
22 }
23
24 int count = 0; // Counter for the number of distinct similarity groups
25 // Count the number of root elements which represents distinct groups
26 for (int i = 0; i < n; ++i) {
27 if (i == findParent(i)) {
28 count++;
29 }
30 }
31 return count;
32 }
33
34 // Helper method to find the root parent of x using path compression
35 private int findParent(int x) {
36 if (parent[x] != x) {
37 parent[x] = findParent(parent[x]);
38 }
39 return parent[x];
40 }
41
42 // Method to check if two strings are similar
43 // Two strings are similar if they are the same, or their difference is only by two characters
44 private boolean isSimilar(String a, String b) {
45 int differences = 0; // Counter for the number of differences between the strings
46 // Iterate through the characters of the strings and count differences
47 for (int i = 0; i < a.length(); ++i) {
48 if (a.charAt(i) != b.charAt(i)) {
49 differences++;
50 }
51 }
52 // Strings are similar if they have 2 or less differences
53 return differences <= 2;
54 }
55}
561#include <vector>
2#include <string>
3
4using std::vector;
5using std::string;
6
7class Solution {
8public:
9 // Parents array for the union-find structure
10 vector<int> parents;
11
12 // Method to find the number of similar groups in the given vector of strings
13 int numSimilarGroups(vector<string>& strs) {
14 int numberOfStrings = strs.size();
15 parents.resize(numberOfStrings);
16
17 // Initialize each string to be its own parent
18 for (int i = 0; i < numberOfStrings; ++i) parents[i] = i;
19
20 // Compare each pair of strings and union them if similar
21 for (int i = 0; i < numberOfStrings; ++i) {
22 for (int j = i + 1; j < numberOfStrings; ++j) {
23 if (isSimilar(strs[i], strs[j])) {
24 int parentI = findParent(i);
25 int parentJ = findParent(j);
26 if (parentI != parentJ) {
27 parents[parentI] = parentJ;
28 }
29 }
30 }
31 }
32
33 // Count the number of distinct groups by checking how many strings are their own parent
34 int numGroups = 0;
35 for (int i = 0; i < numberOfStrings; ++i)
36 if (i == findParent(i))
37 ++numGroups;
38
39 return numGroups;
40 }
41
42 // Helper method to check if two strings are similar
43 // Two strings are similar if they can be made equal by swapping at most two characters.
44 bool isSimilar(string& a, string& b) {
45 int numDifferences = 0;
46
47 for (int i = 0; i < a.size(); ++i) {
48 if (a[i] != b[i]) {
49 ++numDifferences;
50 // If there are more than two differences, the strings cannot be similar
51 if (numDifferences > 2) return false;
52 }
53 }
54
55 return true;
56 }
57
58 // Recursive method to find the root parent of string at index x
59 int findParent(int x) {
60 // Path compression: directly connect the current node to the root
61 if (parents[x] != x) parents[x] = findParent(parents[x]);
62 return parents[x];
63 }
64};
651// Typescript does not use includes or the same namespace syntax as C++
2
3// Declare a global parents array for the union-find structure
4let parents: number[];
5
6// Function to find the number of similar groups in the given array of strings
7function numSimilarGroups(strs: string[]): number {
8 const numberOfStrings: number = strs.length;
9 parents = new Array(numberOfStrings);
10
11 // Initialize each string to be its own parent
12 for (let i = 0; i < numberOfStrings; ++i) parents[i] = i;
13
14 // Compare each pair of strings and union them if similar
15 for (let i = 0; i < numberOfStrings; ++i) {
16 for (let j = i + 1; j < numberOfStrings; ++j) {
17 if (isSimilar(strs[i], strs[j])) {
18 let parentI: number = findParent(i);
19 let parentJ: number = findParent(j);
20 if (parentI !== parentJ) {
21 parents[parentI] = parentJ;
22 }
23 }
24 }
25 }
26
27 // Count the number of distinct groups by checking how many strings are their own parent
28 let numGroups: number = 0;
29 for (let i = 0; i < numberOfStrings; ++i)
30 if (i === findParent(i))
31 ++numGroups;
32
33 return numGroups;
34}
35
36// Helper function to check if two strings are similar
37// Two strings are similar if they can be made equal by swapping at most two characters.
38function isSimilar(a: string, b: string): boolean {
39 let numDifferences: number = 0;
40
41 for (let i = 0; i < a.length; ++i) {
42 if (a[i] !== b[i]) {
43 ++numDifferences;
44 // If there are more than two differences, the strings cannot be similar
45 if (numDifferences > 2) return false;
46 }
47 }
48
49 return true;
50}
51
52// Recursive function to find the root parent of string at index x
53function findParent(x: number): number {
54 // Path compression: directly connect the current node to the root
55 if (parents[x] !== x) parents[x] = findParent(parents[x]);
56 return parents[x];
57}
58Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
Time and Space Complexity
Time Complexity
The given code performs a comparison between each pair of strings within the strs list to determine if they belong to the same group. For each pair of strings, it checks if they differ by at most 2 characters, executing an operation that can be considered as O(L) where L is the length of the string.
There are N strings in the list, and we are comparing each pair of strings. In the worst-case scenario, it requires O(N^2) comparisons. Combining this with the comparison cost for each string gives us a complexity of O(N^2 * L).
However, we have to also consider the union-find algorithm used in the code. In practice, the amortized time complexity of union-find operations (find and union) is O(alpha(N)), where alpha is the Inverse Ackermann function, which grows very slowly and is less than 5 for any practical value of N.
Multiplying the O(N^2) for comparisons by O(alpha(N)) for each union-find operation, we get the total time complexity to be O(N^2 * L * alpha(N)).
Space Complexity
The space complexity is O(N) because the code only uses a parent array p that stores the representative for each string in the group. No additional significant space is required outside the input and the parent array itself.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.