Smallest String With Swaps
Smallest String With Swaps is a medium graphs problem solved with the connected components pattern.
The best approach, optimal (union-find, then sort each group), runs in O((n + p) · α(n) + n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (label propagation, then sort each group) up.
Problem
You are given a string s and a list pairs, where each pairs[i] = [a, b] names two positions of s (0-indexed) whose characters may be swapped.
Each listed swap can be performed as many times as you like and in any order. Return the lexicographically smallest string you can turn s into.
Examples
Example 1
- Input
s = "dcab", pairs = [[0, 3], [1, 2]]- Output
"bacd"- Why
- Positions 0 and 3 can trade, giving "bcad"; positions 1 and 2 can trade, giving "bacd".
Example 2
- Input
s = "zxyw", pairs = [[0, 1], [1, 2], [2, 3]]- Output
"wxyz"- Why
- The pairs chain all four positions together, so the letters can be rearranged freely and sorted.
Example 3
- Input
s = "mango", pairs = []- Output
"mango"- Why
- With no pairs nothing can move.
Constraints
1 <= s.length <= 10^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengthscontains only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (label propagation, then sort each group) | O(n · (n + p) + n log n) | O(n) |
| Optimal (union-find, then sort each group) | O((n + p) · α(n) + n log n) | O(n) |
1Brute force (label propagation, then sort each group)
O(n · (n + p) + n log n)The smallest label can need up to n sweeps to travel along a long chain, and each sweep scans all p pairs; sorting the groups adds n log n.O(n)Labels, the buckets and the output array.Give every index a label equal to itself. Sweep over all pairs again and again, setting both ends of each pair to the smaller of their two labels, until a full sweep changes nothing. At that point every connected group shares one label. Then gather each group's positions (already in increasing order) and letters, sort the letters, and write them back.
- label[i] = i for every index.
- Repeat: for each pair (a, b), set both labels to min(label[a], label[b]); stop when nothing changed in a sweep.
- Bucket the indices by label, in increasing index order.
- For each bucket, sort its letters and place them into its indices left to right.
class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int n = s.length();
int[] label = new int[n];
for (int i = 0; i < n; i++) label[i] = i;
boolean changed = true;
while (changed) {
changed = false;
for (List<Integer> p : pairs) {
int a = p.get(0), b = p.get(1);
int m = Math.min(label[a], label[b]);
if (label[a] != m || label[b] != m) {
label[a] = m;
label[b] = m;
changed = true;
}
}
}
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(label[i], x -> new ArrayList<>()).add(i);
char[] out = new char[n];
for (List<Integer> idx : groups.values()) {
char[] letters = new char[idx.size()];
for (int j = 0; j < idx.size(); j++) letters[j] = s.charAt(idx.get(j));
Arrays.sort(letters);
for (int j = 0; j < idx.size(); j++) out[idx.get(j)] = letters[j];
}
return new String(out);
}
}class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
n = len(s)
label = list(range(n))
changed = True
while changed:
changed = False
for a, b in pairs:
m = min(label[a], label[b])
if label[a] != m or label[b] != m:
label[a] = label[b] = m
changed = True
groups = {}
for i in range(n):
groups.setdefault(label[i], []).append(i)
out = [''] * n
for idx in groups.values():
letters = sorted(s[i] for i in idx)
for j, i in enumerate(idx):
out[i] = letters[j]
return ''.join(out)class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
vector<int> label(n);
for (int i = 0; i < n; i++) label[i] = i;
bool changed = true;
while (changed) {
changed = false;
for (auto& p : pairs) {
int a = p[0], b = p[1];
int m = min(label[a], label[b]);
if (label[a] != m || label[b] != m) {
label[a] = m;
label[b] = m;
changed = true;
}
}
}
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; i++) groups[label[i]].push_back(i);
string out(n, ' ');
for (auto& [key, idx] : groups) {
string letters;
for (int i : idx) letters += s[i];
sort(letters.begin(), letters.end());
for (int j = 0; j < (int)idx.size(); j++) out[idx[j]] = letters[j];
}
return out;
}
};function smallestStringWithSwaps(s, pairs) {
const n = s.length;
const label = Array.from({ length: n }, (_, i) => i);
let changed = true;
while (changed) {
changed = false;
for (const [a, b] of pairs) {
const m = Math.min(label[a], label[b]);
if (label[a] !== m || label[b] !== m) {
label[a] = m;
label[b] = m;
changed = true;
}
}
}
const groups = new Map();
for (let i = 0; i < n; i++) {
if (!groups.has(label[i])) groups.set(label[i], []);
groups.get(label[i]).push(i);
}
const out = new Array(n);
for (const idx of groups.values()) {
const letters = idx.map(i => s[i]).sort();
idx.forEach((i, j) => { out[i] = letters[j]; });
}
return out.join('');
}2Optimal (union-find, then sort each group)
O((n + p) · α(n) + n log n)Each union/find is almost constant (inverse Ackermann); sorting all groups together costs at most n log n.O(n)Parent and size arrays, the groups and the output.Use a disjoint-set union to merge the two ends of every pair in near-constant time. Each root then identifies one connected group of positions. Because any permutation is possible inside a group, the best result puts the group's letters in sorted order into its positions from left to right.
- parent[i] = i; for each pair, union its two ends (path halving in find, union by size).
- Walk i from 0 to n - 1 and append i to the list of find(i).
- For each list, sort the letters at those positions and write them back in order.
class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int n = s.length();
int[] parent = new int[n], size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
for (List<Integer> p : pairs) {
int a = find(parent, p.get(0)), b = find(parent, p.get(1));
if (a == b) continue;
if (size[a] < size[b]) { int t = a; a = b; b = t; }
parent[b] = a;
size[a] += size[b];
}
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(find(parent, i), x -> new ArrayList<>()).add(i);
char[] out = new char[n];
for (List<Integer> idx : groups.values()) {
char[] letters = new char[idx.size()];
for (int j = 0; j < idx.size(); j++) letters[j] = s.charAt(idx.get(j));
Arrays.sort(letters);
for (int j = 0; j < idx.size(); j++) out[idx.get(j)] = letters[j];
}
return new String(out);
}
private int find(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
n = len(s)
parent = list(range(n))
size = [1] * n
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in pairs:
ra, rb = find(a), find(b)
if ra == rb:
continue
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
groups = {}
for i in range(n):
groups.setdefault(find(i), []).append(i)
out = [''] * n
for idx in groups.values():
letters = sorted(s[i] for i in idx)
for j, i in enumerate(idx):
out[i] = letters[j]
return ''.join(out)class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
vector<int> parent(n), size(n, 1);
for (int i = 0; i < n; i++) parent[i] = i;
for (auto& p : pairs) {
int a = find(parent, p[0]), b = find(parent, p[1]);
if (a == b) continue;
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
}
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; i++) groups[find(parent, i)].push_back(i);
string out(n, ' ');
for (auto& [root, idx] : groups) {
string letters;
for (int i : idx) letters += s[i];
sort(letters.begin(), letters.end());
for (int j = 0; j < (int)idx.size(); j++) out[idx[j]] = letters[j];
}
return out;
}
private:
int find(vector<int>& parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
};function smallestStringWithSwaps(s, pairs) {
const n = s.length;
const parent = Array.from({ length: n }, (_, i) => i);
const size = new Array(n).fill(1);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (const [p0, p1] of pairs) {
let a = find(p0), b = find(p1);
if (a === b) continue;
if (size[a] < size[b]) [a, b] = [b, a];
parent[b] = a;
size[a] += size[b];
}
const groups = new Map();
for (let i = 0; i < n; i++) {
const r = find(i);
if (!groups.has(r)) groups.set(r, []);
groups.get(r).push(i);
}
const out = new Array(n);
for (const idx of groups.values()) {
const letters = idx.map(i => s[i]).sort();
idx.forEach((i, j) => { out[i] = letters[j]; });
}
return out.join('');
}Edge cases to test
- No pairs at all: the string is returned unchanged
- A pair that connects an index with itself
- The same pair listed several times, or in both orders
- Pairs that link positions only indirectly, like (0, 4) and (4, 2)
- A single character
Hints
Hint 1
A swap can be used any number of times. If position a can swap with b and b with c, can the letter at a end up at c?
Hint 2
Treat indices as nodes and pairs as edges. Inside one connected group, any arrangement of the group's letters is reachable.
Hint 3
Find the groups (union-find is a good fit), then sort each group's letters and write them back into the group's positions from left to right.
FAQ
What is the best time complexity for Smallest String With Swaps?
Optimal (union-find, then sort each group) runs in O((n + p) · α(n) + n log n) time and O(n) extra space. Each union/find is almost constant (inverse Ackermann); sorting all groups together costs at most n log n.
Which pattern does Smallest String With Swaps use?
It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.
Is there a brute force solution for Smallest String With Swaps?
Yes. Brute force (label propagation, then sort each group) takes O(n · (n + p) + n log n) time and O(n) space. Give every index a label equal to itself.
Which edge cases should I test for Smallest String With Swaps?
No pairs at all: the string is returned unchanged; A pair that connects an index with itself; The same pair listed several times, or in both orders; Pairs that link positions only indirectly, like (0, 4) and (4, 2); A single character.