# Groups of Strings
**Difficulty:** HARD
[External](https://leetcode.com/problems/groups-of-strings)
Canonical: https://scaleengineer.com/dsa/problems/groups-of-strings
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** String
**Companies:** [Lowe's](https://scaleengineer.com/companies/lowe's)
---
## Problem
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 `s1` with 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 groups_ `words` _can be divided into, and_
* `ans[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 * 104`
* `1 <= words[i].length <= 26`
* `words[i]` consists of lowercase English letters only.
* No letter occurs more than once in `words[i]`.

# Approaches
## Brute-Force with Pairwise Comparison
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).
**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.
**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 (`N` up to 2 * 10^4).
### Explanation
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.

```java
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.
}
```
### Algorithm
- Convert each string in `words` into 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) == 2` and `Integer.bitCount(mask1) == Integer.bitCount(mask2)`, two bits are different but the total number of set bits is the same, meaning one character was replaced.
- If two masks are connected, perform a `union` operation 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.

## Optimized Connection Finding with Union-Find
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.
**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.
**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.
### Explanation
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).

1.  **Preprocessing:** As before, we convert each word to a bitmask and store the frequencies in a `Map<Integer, Integer> maskToCount`.

2.  **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`.

3.  **Finding Connections:** We iterate through each unique mask `m` in `maskToCount.keySet()`.
    - To handle **deletion/addition**, we iterate through the 26 possible bit positions. If a bit `i` is set in `m`, we flip it to 0 to create a `deletedMask`. If this `deletedMask` exists in our `maskToCount` map, we union the sets for `m` and `deletedMask`.
    - To handle **replacement**, we use a nested loop. The outer loop iterates through bits `i` that are set in `m` (character to remove). The inner loop iterates through bits `j` that are not set in `m` (character to add). We form a `replacedMask` by flipping both bits. If this `replacedMask` exists in our map, we union the sets.

This process ensures that all connections are found without redundant comparisons. The final answer is extracted from the Union-Find data structure.

```java
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;
    }
}
```
### 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 `mask` from 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 the `mask`, generate a potential neighbor by removing it: `deletedMask = mask ^ (1 << i)`. If `deletedMask` exists in `maskToCount`, they are connected, so we call `union(mask, deletedMask)`.
  - **Replacement:** For each character to remove (set bit `i`) and each character to add (unset bit `j`), generate a potential neighbor: `replacedMask = (mask ^ (1 << i)) | (1 << j)`. If `replacedMask` exists in `maskToCount`, we call `union(mask, replacedMask)`.
- Note that the 'addition' case is implicitly handled. If `m1` can be formed by adding a character to `m2`, this connection will be found when the algorithm processes `m1` and considers deleting a character from it to form `m2`.
- 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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]

```