Groups of Strings
HardPrompt
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].
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as finding connected components in a graph. The nodes of the graph are the unique strings (represented by bitmasks), and an edge exists between two nodes if the corresponding strings are 'connected' according to the problem's definition. A brute-force way to build this graph is to check every possible pair of strings for a connection. The Union-Find data structure is then used to efficiently track the connected components (groups).
Algorithm
- Convert each string in
wordsinto a bitmask representation. A 26-bit integer can represent the set of characters, where the i-th bit is 1 if the character 'a' + i is present. - Store the unique bitmasks and the frequency of each mask (how many original strings map to it) in a hash map.
- Create a list of all unique bitmasks.
- Initialize a Union-Find data structure, with each unique mask as a separate set. The initial size of each set is the frequency of the corresponding mask.
- Iterate through all pairs of unique bitmasks
(mask1, mask2). - For each pair, check if they are connected:
- The connection condition can be checked using bitwise operations. Let
xor = mask1 ^ mask2. - Add/Delete: If
Integer.bitCount(xor) == 1, one bit is different, meaning one character was added or deleted. - Replace: If
Integer.bitCount(xor) == 2andInteger.bitCount(mask1) == Integer.bitCount(mask2), two bits are different but the total number of set bits is the same, meaning one character was replaced.
- The connection condition can be checked using bitwise operations. Let
- If two masks are connected, perform a
unionoperation on them in the Union-Find structure. - After checking all pairs, the number of disjoint sets in the Union-Find structure is the number of groups, and the maximum size of any set is the size of the largest group.
Walkthrough
First, we preprocess the input words array. Since the connection rules depend on the set of characters, not their order, we can represent each string as a 26-bit integer, or a 'bitmask'. The i-th bit of the mask is set to 1 if the i-th letter of the alphabet is in the string. We use a hash map to store each unique mask and the count of strings that produce it.
Next, we iterate through every possible pair of unique masks. For each pair, we check if they are connected. Two masks m1 and m2 are connected if m2 can be formed from m1 by adding, deleting, or replacing a single character. This check can be done efficiently with bitwise operations. If they are connected, we merge their corresponding sets using a Union-Find data structure.
After iterating through all pairs, the Union-Find structure holds the final grouping. The number of groups is the number of disjoint sets, and the size of the largest group is the maximum size recorded in any set.
class Solution { public int[] groupStrings(String[] words) { Map<Integer, Integer> maskToCount = new HashMap<>(); for (String word : words) { int mask = 0; for (char c : word.toCharArray()) { mask |= (1 << (c - 'a')); } maskToCount.put(mask, maskToCount.getOrDefault(mask, 0) + 1); } List<Integer> uniqueMasks = new ArrayList<>(maskToCount.keySet()); UnionFind uf = new UnionFind(maskToCount); for (int i = 0; i < uniqueMasks.size(); i++) { for (int j = i + 1; j < uniqueMasks.size(); j++) { int mask1 = uniqueMasks.get(i); int mask2 = uniqueMasks.get(j); if (isConnected(mask1, mask2)) { uf.union(mask1, mask2); } } } return new int[]{uf.getNumGroups(), uf.getMaxGroupSize()}; } private boolean isConnected(int mask1, int mask2) { int xor = mask1 ^ mask2; // Add/delete: one bit difference if (Integer.bitCount(xor) == 1) { return true; } // Replace: two bits difference, same total number of set bits if (Integer.bitCount(xor) == 2 && Integer.bitCount(mask1) == Integer.bitCount(mask2)) { return true; } return false; } // A Union-Find implementation is needed here. // See the optimal approach for a sample implementation.}Complexity
Time
O(N*L + U^2), where N is the number of words, L is the maximum length of a word, and U is the number of unique words. The `N*L` term comes from preprocessing the words into bitmasks. The `U^2` term comes from iterating through all pairs of unique masks. Since U can be up to N, the complexity is dominated by O(N^2), which will time out.
Space
O(N), where N is the number of strings in `words`. This space is used for the `maskToCount` map, the list of unique masks, and the Union-Find data structure.
Trade-offs
Pros
Conceptually simple and easy to understand.
Correctly solves the problem for smaller inputs.
Cons
The time complexity is quadratic with respect to the number of unique strings, which is too slow for the given constraints (
Nup to 2 * 10^4).
This approach significantly optimizes the process of finding connections. Instead of comparing every pair of masks, which is inefficient (O(U^2)), we take each mask and proactively generate all possible masks that could be connected to it by one of the three operations (add, delete, replace). We then check if these generated masks actually exist in our input set. This avoids the quadratic complexity and leads to a much faster solution.
Algorithm
- Convert each string to a bitmask and store its frequency in a map
maskToCount, same as the brute-force approach. - Initialize a Union-Find data structure where each unique mask is a separate component. The initial size of each component is set to the frequency of the mask.
- Iterate through each unique
maskfrom our map. - For each
mask, instead of comparing it with all others, we generate all possible masks that could be connected to it:- Deletion: For each character (set bit
i) in themask, generate a potential neighbor by removing it:deletedMask = mask ^ (1 << i). IfdeletedMaskexists inmaskToCount, they are connected, so we callunion(mask, deletedMask). - Replacement: For each character to remove (set bit
i) and each character to add (unset bitj), generate a potential neighbor:replacedMask = (mask ^ (1 << i)) | (1 << j). IfreplacedMaskexists inmaskToCount, we callunion(mask, replacedMask).
- Deletion: For each character (set bit
- Note that the 'addition' case is implicitly handled. If
m1can be formed by adding a character tom2, this connection will be found when the algorithm processesm1and considers deleting a character from it to formm2. - After iterating through all masks and their potential neighbors, the Union-Find structure will represent the final groups. The result is then the number of disjoint sets and the maximum size of a set.
Walkthrough
The core idea is to avoid the O(U^2) pairwise checks. For each unique mask m from the input, we can find all its neighbors in constant time (relative to the alphabet size, which is 26).
-
Preprocessing: As before, we convert each word to a bitmask and store the frequencies in a
Map<Integer, Integer> maskToCount. -
Union-Find: We use a Union-Find data structure to manage the groups. A hash map-based implementation is suitable since the masks are not necessarily contiguous integers. Each mask is initialized in its own set, with a size equal to its frequency from
maskToCount. -
Finding Connections: We iterate through each unique mask
minmaskToCount.keySet().- To handle deletion/addition, we iterate through the 26 possible bit positions. If a bit
iis set inm, we flip it to 0 to create adeletedMask. If thisdeletedMaskexists in ourmaskToCountmap, we union the sets formanddeletedMask. - To handle replacement, we use a nested loop. The outer loop iterates through bits
ithat are set inm(character to remove). The inner loop iterates through bitsjthat are not set inm(character to add). We form areplacedMaskby flipping both bits. If thisreplacedMaskexists in our map, we union the sets.
- To handle deletion/addition, we iterate through the 26 possible bit positions. If a bit
This process ensures that all connections are found without redundant comparisons. The final answer is extracted from the Union-Find data structure.
class Solution { public int[] groupStrings(String[] words) { Map<Integer, Integer> maskToCount = new HashMap<>(); for (String word : words) { int mask = 0; for (char c : word.toCharArray()) { mask |= (1 << (c - 'a')); } maskToCount.put(mask, maskToCount.getOrDefault(mask, 0) + 1); } UnionFind uf = new UnionFind(maskToCount); for (int mask : maskToCount.keySet()) { // Case 1: Deletion (implicitly handles addition) for (int i = 0; i < 26; i++) { if ((mask & (1 << i)) != 0) { // If i-th bit is set int deletedMask = mask ^ (1 << i); if (maskToCount.containsKey(deletedMask)) { uf.union(mask, deletedMask); } } } // Case 2: Replacement for (int i = 0; i < 26; i++) { if ((mask & (1 << i)) != 0) { // Character to remove for (int j = 0; j < 26; j++) { if ((mask & (1 << j)) == 0) { // Character to add int replacedMask = (mask ^ (1 << i)) | (1 << j); if (maskToCount.containsKey(replacedMask)) { uf.union(mask, replacedMask); } } } } } } return new int[]{uf.getNumGroups(), uf.getMaxGroupSize()}; }} class UnionFind { private Map<Integer, Integer> parent; private Map<Integer, Integer> groupSize; private int numGroups; public UnionFind(Map<Integer, Integer> initialItems) { parent = new HashMap<>(); groupSize = new HashMap<>(); for (Map.Entry<Integer, Integer> entry : initialItems.entrySet()) { int mask = entry.getKey(); int count = entry.getValue(); parent.put(mask, mask); groupSize.put(mask, count); } numGroups = initialItems.size(); } public int find(int i) { if (parent.get(i) == i) { return i; } int root = find(parent.get(i)); parent.put(i, root); // Path compression return root; } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { // Union by size if (groupSize.get(rootI) < groupSize.get(rootJ)) { int temp = rootI; rootI = rootJ; rootJ = temp; } parent.put(rootJ, rootI); groupSize.put(rootI, groupSize.get(rootI) + groupSize.get(rootJ)); numGroups--; } } public int getNumGroups() { return numGroups; } public int getMaxGroupSize() { int maxSize = 0; for (int mask : parent.keySet()) { if (parent.get(mask) == mask) { // It's a root maxSize = Math.max(maxSize, groupSize.get(mask)); } } return maxSize; }}Complexity
Time
O(N*L + U*C^2), where N is the number of words, L is the max length, U is the number of unique masks, and C is the alphabet size (26). Since L and C are small constants, the complexity simplifies to O(N*L). This is dominated by the initial processing of strings.
Space
O(N), where N is the number of strings. Space is required for the `maskToCount` map and the Union-Find data structure, both of which can store up to N unique items.
Trade-offs
Pros
Highly efficient, with a time complexity linear in the number of words.
Scales well and passes the given constraints.
Cons
The implementation is more complex than the brute-force approach due to the logic for generating potential neighbors.
Solutions
Solution
class Solution {private Map<Integer, Integer> p;private Map<Integer, Integer> size;private int mx;private int n;public int[] groupStrings(String[] words) { p = new HashMap<>(); size = new HashMap<>(); n = words.length; mx = 0; for (String word : words) { int x = 0; for (char c : word.toCharArray()) { x |= 1 << (c - 'a'); } p.put(x, x); size.put(x, size.getOrDefault(x, 0) + 1); mx = Math.max(mx, size.get(x)); if (size.get(x) > 1) { --n; } } for (int x : p.keySet()) { for (int i = 0; i < 26; ++i) { union(x, x ^ (1 << i)); if (((x >> i) & 1) != 0) { for (int j = 0; j < 26; ++j) { if (((x >> j) & 1) == 0) { union(x, x ^ (1 << i) | (1 << j)); } } } } } return new int[]{n, mx}; }private int find(int x) { if (p.get(x) != x) { p.put(x, find(p.get(x))); } return p.get(x); }private void union(int a, int b) { if (!p.containsKey(b)) { return; } int pa = find(a), pb = find(b); if (pa == pb) { return; } p.put(pa, pb); size.put(pb, size.get(pb) + size.get(pa)); mx = Math.max(mx, size.get(pb)); --n; }}class Solution {public: int mx, n; vector<int> groupStrings(vector<string> &words) { unordered_map<int, int> p; unordered_map<int, int> size; mx = 0; n = words.size(); for (auto &word : words) { int x = 0; for (auto &c : word) x |= 1 << (c - 'a'); p[x] = x; ++size[x]; mx = max(mx, size[x]); if (size[x] > 1) --n; } for (auto &[x, _] : p) { for (int i = 0; i < 26; ++i) { unite(x, x ^ (1 << i), p, size); if ((x >> i) & 1) { for (int j = 0; j < 26; ++j) { if (((x >> j) & 1) == 0) unite(x, x ^ (1 << i) | (1 << j), p, size); } } } } return {n, mx}; } int find(int x, unordered_map<int, int> &p) { if (p[x] != x) p[x] = find(p[x], p); return p[x]; } void unite(int a, int b, unordered_map<int, int> &p, unordered_map<int, int> &size) { if (!p.count(b)) return; int pa = find(a, p), pb = find(b, p); if (pa == pb) return; p[pa] = pb; size[pb] += size[pa]; mx = max(mx, size[pb]); --n; }};class Solution: def groupStrings(self, words: List[str]) -> List[int]: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): nonlocal mx, n if b not in p: return pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] mx = max(mx, size[pb]) n -= 1 p = {} size = Counter() n = len(words) mx = 0 for word in words: x = 0 for c in word: x |= 1 << (ord(c) - ord('a')) p[x] = x size[x] += 1 mx = max(mx, size[x]) if size[x] > 1: n -= 1 for x in p . keys(): for i in range(26): union(x, x ^ (1 << i)) if (x >> i) & 1: for j in range(26): if ((x >> j) & 1) == 0: union(x, x ^ (1 << i) | (1 << j)) return [n, mx]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.