MediumNo. 1202
Smallest String With Swaps — LeetCode 1202 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table, String, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times.
Example
- Input
- s = "dcab", pairs = [[0,3],[1,2]]
- Output
- "bacd"
Python solution
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(s)
p = list(range(n))
for a, b in pairs:
p[find(a)] = find(b)
d = defaultdict(list)
for i, c in enumerate(s):
d[find(i)].append(c)
for i in d.keys():
d[i].sort(reverse=True)
return "".join(d[find(i)].pop() for i in range(n))Complexity
- Time
- O(n × log n + m × α(m))
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1202. Smallest String With Swaps is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 0959 | Regions Cut By Slashes | Medium |
| 2368 | Reachable Nodes With Restrictions | Medium |
Frequently asked questions
- How hard is LeetCode 1202. Smallest String With Swaps?
LeetCode 1202. Smallest String With Swaps is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1202. Smallest String With Swaps?
The Python solution on this page runs in O(n × log n + m × α(m)).
- What is the space complexity of LeetCode 1202. Smallest String With Swaps?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1202. Smallest String With Swaps cover?
LeetCode 1202. Smallest String With Swaps is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table, String and Sorting on LeetCode.