Groups of Strings - Solution & Explanation
Problem Statement
You are given a 0-indexed array of strings words. Each string consists of lowercase English letters only. No letter occurs more than once in any string of words.
Two strings s1 and s2 are said to be connected if the set of letters of s2 can be obtained from the set of letters of s1 by any one of the following operations:
- Adding exactly one letter to the set of the letters of
s1. - Deleting exactly one letter from the set of the letters of
s1. - Replacing exactly one letter from the set of the letters of
s1with any letter, including itself.
The array words can be divided into one or more non-intersecting groups. A string belongs to a group if any one of the following is true:
- It is connected to at least one other string of the group.
- It is the only string present in the group.
Note that the strings in words should be grouped in such a manner that a string belonging to a group cannot be connected to a string present in any other group. It can be proved that such an arrangement is always unique.
Return an array ans of size 2 where:
ans[0]is the maximum number of groupswordscan be divided into, andans[1]is the size of the largest group.
Example 1:
Input: words = ["a","b","ab","cde"] Output: [2,3] Explanation: - words[0] can be used to obtain words[1] (by replacing 'a' with 'b'), and words[2] (by adding 'b'). So words[0] is connected to words[1] and words[2]. - words[1] can be used to obtain words[0] (by replacing 'b' with 'a'), and words[2] (by adding 'a'). So words[1] is connected to words[0] and words[2]. - words[2] can be used to obtain words[0] (by deleting 'b'), and words[1] (by deleting 'a'). So words[2] is connected to words[0] and words[1]. - words[3] is not connected to any string in words. Thus, words can be divided into 2 groups ["a","b","ab"] and ["cde"]. The size of the largest group is 3.
Example 2:
Input: words = ["a","ab","abc"] Output: [1,3] Explanation: - words[0] is connected to words[1]. - words[1] is connected to words[0] and words[2]. - words[2] is connected to words[1]. Since all strings are connected to each other, they should be grouped together. Thus, the size of the largest group is 3.
Constraints:
1 <= words.length <= 2 * 1041 <= words[i].length <= 26words[i]consists of lowercase English letters only.- No letter occurs more than once in
words[i].
Approach Overview
Problem Overview: You are given an array of lowercase strings. Two strings belong to the same group if you can transform one into the other by adding, removing, or replacing exactly one character. The task is to compute the number of groups and the size of the largest group.
Approach 1: Union-Find with Bitmask Representation (O(n * 26) time, O(n) space)
Each string contains unique characters, which means the set of characters can be encoded as a 26-bit integer. Bit i indicates whether character 'a' + i exists in the string. Using this representation, adding or removing a character becomes a single bit toggle operation. You maintain a hash map from bitmask to the index of a string and use a Union-Find structure to merge connected strings.
For every string mask, generate neighbors by toggling each of the 26 bits to simulate adding or removing a character. If the resulting mask exists in the map, union the two indices. Replacement is handled by removing one bit and adding another; this can be detected by checking intermediate masks generated during deletion. Since each string generates at most 26 variations, the algorithm runs in roughly O(n * 26) operations with near-constant Union-Find merges.
This approach is highly efficient because bit operations are constant time and the disjoint-set structure quickly merges connected components. It works especially well when the alphabet size is small and fixed. The technique combines bit manipulation with connectivity tracking.
Approach 2: Graph Representation and BFS/DFS (O(n * 26) average, higher constant factors, O(n) space)
Another way to view the problem is as a graph where each string is a node and edges connect strings that differ by one allowed operation. Convert every string into a bitmask and store them in a hash set for quick lookup. For each node, generate all possible masks that differ by adding, removing, or replacing one character. If a generated mask exists, connect the nodes.
Once the implicit graph is built, run BFS or DFS from each unvisited node to discover a connected component. Track the component size while traversing neighbors generated through bit operations. Although the theoretical complexity is similar, repeatedly exploring neighbors during traversal leads to larger constant overhead compared with the Union-Find method.
This method is conceptually simpler because it treats the problem as a standard connected-components search on a graph derived from string transformations.
Recommended for interviews: The Union-Find with bitmask approach is what most interviewers expect for this problem. It demonstrates understanding of bit-level encoding, efficient neighbor generation, and dynamic connectivity. A brute-force pairwise comparison shows the transformation rule, but scaling it to large input requires the optimized bitmask + Union-Find design.
Approach 1: Approach 1: Union-Find with Bitmask Representation
This approach uses the Union-Find data structure to manage the connections between words. Each string is represented as a bitmask, where each bit represents whether a particular character ('a' to 'z') is present in the string. Connections are determined by checking if two strings differ by an addition, deletion, or replacement of a single character, which can be efficiently checked using bitwise operations.
The C solution uses bit manipulation to convert each string into a bitmask. It utilizes a Union-Find structure to group connected components efficiently. We iterate through each word, compute possible mutations via bit manipulation, and union the groups accordingly.
Complexity
Time Complexity: O(N * 26), where N is the number of words. Space Complexity: O(N) due to the Union-Find structure.
Approach 2: Approach 2: Graph Representation and BFS/DFS
This approach likens the problem to finding connected components in a graph. Each word is a node, and edges represent the possibility of transformation between words. Using BFS or DFS, traverse each component to find its size and number.
The solution constructs a graph where each node (word) can be linked to another if a valid transformation exists. DFS traverses this graph to determine the size and count of connected components.
Complexity
Time Complexity: O(N^2 * K), where N is the number of words and K is the average length of words. Space Complexity: O(N^2), for the adjacency matrix representation.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Union-Find with Bitmask Representation | Time Complexity: O(N * 26), where N is the number of words. Space Complexity: O(N) due to the Union-Find structure. |
| Approach 2: Graph Representation and BFS/DFS | Time Complexity: O(N^2 * K), where N is the number of words and K is the average length of words. Space Complexity: O(N^2), for the adjacency matrix representation. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find with Bitmask Representation | O(n * 26) | O(n) | Best general solution. Efficient grouping using bit operations and disjoint sets. |
| Graph Representation with BFS/DFS | O(n * 26) average | O(n) | Useful when modeling the problem as connected components for conceptual clarity. |
Video Solution
Groups of Strings| Leeetcode 2157 | Contest 278 | Union Find Bit Manipulation 🔥 🔥 🔥 • Coding Decoded • 1,598 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Groups of Strings easy or hard?
Groups of Strings Python/Java solution
How to solve Groups of Strings in O(n)?
What is the best approach for Groups of Strings?
Is Groups of Strings asked at Google/Amazon/Meta?
What data structure is used in Groups of Strings?
What is the time complexity of Groups of Strings?
Ready to solve this problem?
Practice Groups of Strings with our built-in code editor and test cases.
Practice on FleetCode