HardNo. 2157
Groups of Strings — LeetCode 2157 Python Solution
- Pattern
- Union-Find
- Topics
- Bit Manipulation, Union Find, String
- Reading time
- 7 min
- Source
- leetcode.com
The problem
You are given a 0-indexed array of strings words. Each string consists of lowercase English letters only.
Example
- 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].
Python solution
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]Complexity
- Time
- Near O(n) (amortized)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2157. Groups of Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1061 | Lexicographically Smallest Equivalent String | Medium |
| 0803 | Bricks Falling When Hit | Hard |
| 1627 | Graph Connectivity With Threshold | Hard |
| 1697 | Checking Existence of Edge Length Limited Paths | Hard |
| 1998 | GCD Sort of an Array | Hard |
| 2382 | Maximum Segment Sum After Removals | Hard |
Frequently asked questions
- How hard is LeetCode 2157. Groups of Strings?
LeetCode 2157. Groups of Strings is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2157. Groups of Strings?
The Python solution on this page runs in Near O(n) (amortized).
- What is the space complexity of LeetCode 2157. Groups of Strings?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2157. Groups of Strings cover?
LeetCode 2157. Groups of Strings is tagged Bit Manipulation, Union Find and String on LeetCode.