In this guide, you will get 2157. Groups of Strings LeetCode Solution with the best time and space complexity. The solution to Groups of Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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].
Complexity Analysis
Time Complexity: O(26n \cdot \alpha(n))
Space Complexity: O(26n)
2157. Groups of Strings LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : count(n), id(n), sz(n, 1) {
iota(id.begin(), id.end(), 0);
}
void unionBySize(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (sz[i] < sz[j]) {
sz[j] += sz[i];
id[i] = j;
} else {
sz[i] += sz[j];
id[j] = i;
}
--count;
}
int getCount() const {
return count;
}
int getMaxSize() const {
return ranges::max(sz);
}
private:
int count;
vector<int> id;
vector<int> sz;
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};
class Solution {
public:
vector<int> groupStrings(vector<string>& words) {
UnionFind uf(words.size());
unordered_map<int, int> maskToIndex;
unordered_map<int, int> deletedMaskToIndex;
for (int i = 0; i < words.size(); ++i) {
const int mask = getMask(words[i]);
for (int j = 0; j < 26; ++j)
if (mask >> j & 1) {
// Going to delete this bit.
const int m = mask ^ 1 << j;
if (const auto it = maskToIndex.find(m); it != maskToIndex.cend())
uf.unionBySize(i, it->second);
if (const auto it = deletedMaskToIndex.find(m);
it != deletedMaskToIndex.cend())
uf.unionBySize(i, it->second);
else
deletedMaskToIndex[m] = i;
} else {
// Going to add this bit.
const int m = mask | 1 << j;
if (const auto it = maskToIndex.find(m); it != maskToIndex.cend())
uf.unionBySize(i, it->second);
}
maskToIndex[mask] = i;
}
return {uf.getCount(), uf.getMaxSize()};
}
private:
int getMask(const string& s) {
int mask = 0;
for (const char c : s)
mask |= 1 << c - 'a';
return mask;
}
}; /* code provided by PROGIEZ */
2157. Groups of Strings LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
count = n;
id = new int[n];
sz = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
for (int i = 0; i < n; ++i)
sz[i] = 1;
}
public void unionBySize(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (sz[i] < sz[j]) {
sz[j] += sz[i];
id[i] = j;
} else {
sz[i] += sz[j];
id[j] = i;
}
--count;
}
public int getCount() {
return count;
}
public int getMaxSize() {
return Arrays.stream(sz).max().getAsInt();
}
private int count;
private int[] id;
private int[] sz;
private int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}
class Solution {
public int[] groupStrings(String[] words) {
UnionFind uf = new UnionFind(words.length);
Map<Integer, Integer> maskToIndex = new HashMap<>();
Map<Integer, Integer> deletedMaskToIndex = new HashMap<>();
for (int i = 0; i < words.length; ++i) {
final int mask = getMask(words[i]);
for (int j = 0; j < 26; ++j)
if ((mask >> j & 1) == 1) {
// Going to delete this bit.
final int m = mask ^ 1 << j;
if (maskToIndex.containsKey(m))
uf.unionBySize(i, maskToIndex.get(m));
if (deletedMaskToIndex.containsKey(m))
uf.unionBySize(i, deletedMaskToIndex.get(m));
else
deletedMaskToIndex.put(m, i);
} else {
// Going to add this bit.
final int m = mask | 1 << j;
if (maskToIndex.containsKey(m))
uf.unionBySize(i, maskToIndex.get(m));
}
maskToIndex.put(mask, i);
}
return new int[] {uf.getCount(), uf.getMaxSize()};
}
private int getMask(final String s) {
int mask = 0;
for (final char c : s.toCharArray())
mask |= 1 << c - 'a';
return mask;
}
} // code provided by PROGIEZ
2157. Groups of Strings LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.count = n
self.id = list(range(n))
self.sz = [1] * n
def unionBySize(self, u: int, v: int) -> None:
i = self._find(u)
j = self._find(v)
if i == j:
return
if self.sz[i] < self.sz[j]:
self.sz[j] += self.sz[i]
self.id[i] = j
else:
self.sz[i] += self.sz[j]
self.id[j] = i
self.count -= 1
def _find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self._find(self.id[u])
return self.id[u]
class Solution:
def groupStrings(self, words: list[str]) -> list[int]:
uf = UnionFind(len(words))
def getMask(s: str) -> int:
mask = 0
for c in s:
mask |= 1 << ord(c) - ord('a')
return mask
def getAddedMasks(mask: int):
for i in range(26):
if not (mask >> i & 1):
yield mask | 1 << i
def getDeletedMasks(mask: int):
for i in range(26):
if mask >> i & 1:
yield mask ^ 1 << i
maskToIndex = {getMask(word): i for i, word in enumerate(words)}
deletedMaskToIndex = {}
for i, word in enumerate(words):
mask = getMask(word)
for m in getAddedMasks(mask):
if m in maskToIndex:
uf.unionBySize(i, maskToIndex[m])
for m in getDeletedMasks(mask):
if m in maskToIndex:
uf.unionBySize(i, maskToIndex[m])
if m in deletedMaskToIndex:
uf.unionBySize(i, deletedMaskToIndex[m])
else:
deletedMaskToIndex[m] = i
return [uf.count, max(uf.sz)] # code by PROGIEZ
