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.strs have the same length and are anagrams of each other.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.
This solution uses the Union-Find data structure to keep track of connected string groups. The areSimilar() function calculates string similarity by counting character mismatches. If a mismatch is found more than twice, the strings are not similar. The main function initializes the parents and processes connections through the union-find operations to count the disjoint sets.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * k) where n is the number of strings and k is the average length of the strings.
Space Complexity: O(n), storing the parent array.
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.
This C solution employs DFS to exhaustively search connected components formed by similar strings. We use a boolean array to track visited nodes and explore each group fully once a node from that group is encountered.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * k) where n is the number of strings and k is the length of strings.
Space Complexity: O(n) to maintain the visited array.
| Approach | Complexity |
|---|---|
| Union-Find Approach | Time Complexity: O(n^2 * k) where n is the number of strings and k is the average length of the strings. |
| Depth-First Search (DFS) Approach | Time Complexity: O(n^2 * k) where n is the number of strings and k is the length of strings. |
Group Anagrams - Categorize Strings by Count - Leetcode 49 • NeetCode • 611,562 views views
Watch 9 more video solutions →Practice Similar String Groups with our built-in code editor and test cases.
Practice on FleetCode