Smallest String With Swaps — Solution in Python, Java & C++
Smallest String With Swaps solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Smallest String With Swaps is a medium coding problem on strings, hash table and sorting, asked in Amazon, Google, Uber and PhonePe interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sorting, Union Find
- Asked at: Amazon, Google, Uber, PhonePe, Rubrik, Palantir
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and a list pairs of index pairs. You may swap the characters at any listed pair any number of times, in any order.
Return the lexicographically smallest string reachable this way.
Example 1
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: bacd
Explanation: Indices 0 and 3 can swap, as can 1 and 2, giving two independent pairs.
Example 2
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: abcd
Explanation: The third pair links everything into one group, so all four characters can be sorted freely.
Example 3
Input: s = "cba", pairs = [[0,1],[1,2]]
Output: abc
Constraints
1 <= s.length <= 1000000 <= pairs.length <= 1000000 <= pairs[i][0], pairs[i][1] < s.lengths consists of lowercase English letters.
Hints for Smallest String With Swaps
Hint 1
Repeated swaps mean the pairs define connected components of indices.
Hint 2
Within one component any permutation of its characters is reachable.
Hint 3
So sort each component's characters and write them back into that component's indices in sorted order.
How to solve Smallest String With Swaps
Swapping along edges any number of times generates every permutation within a connected component. So the smallest string sorts each component's multiset of characters into its component's sorted index list.
Approach
- Union the indices of every pair with a disjoint-set structure.
- Group the indices by their component root.
- For each group, collect its characters, sort them, and write them back into the group's indices in increasing index order.
Why it works
Transpositions along a connected graph generate the full symmetric group on its vertices, so any arrangement of a component's characters is reachable. Placing the smallest available character at the smallest index of the component is greedily optimal and cannot be beaten, because positions in different components are independent.
Complexity
- Time —
O(n log n + p α(n)) - Space —
O(n)
Pitfalls
- Swapping only the listed pairs once misses arrangements that need a chain of swaps.
- Sorting the whole string ignores the component boundaries and is wrong whenever the graph is disconnected.
- Path compression matters: without it the union-find degrades badly at the stated limits.
Reference solution
Python
from typing import List
def smallestStringWithSwaps(s: str, pairs: List[List[int]]) -> str:
n = len(s)
parent = list(range(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:
parent[ra] = rb
groups = {}
for i in range(n):
groups.setdefault(find(i), []).append(i)
out = list(s)
for idx in groups.values():
chars = sorted(s[i] for i in idx)
for t, i in enumerate(idx):
out[i] = chars[t]
return "".join(out)Java
public static String smallestStringWithSwaps(String s, int[][] pairs) {
int n = s.length();
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int[] p : pairs) {
int a = findRoot(parent, p[0]);
int b = findRoot(parent, p[1]);
if (a != b) parent[a] = b;
}
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(findRoot(parent, i), z -> new ArrayList<>()).add(i);
char[] out = s.toCharArray();
for (List<Integer> idx : groups.values()) {
char[] chars = new char[idx.size()];
for (int t = 0; t < idx.size(); t++) chars[t] = s.charAt(idx.get(t));
Arrays.sort(chars);
for (int t = 0; t < idx.size(); t++) out[idx.get(t)] = chars[t];
}
return new String(out);
}
static int findRoot(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}C++
static int findRootSwap(vector<int>& parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = (int) s.size();
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
for (auto& p : pairs) {
int a = findRootSwap(parent, p[0]);
int b = findRootSwap(parent, p[1]);
if (a != b) parent[a] = b;
}
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; i++) groups[findRootSwap(parent, i)].push_back(i);
string out = s;
for (auto& g : groups) {
string chars;
for (int i : g.second) chars += s[i];
sort(chars.begin(), chars.end());
for (size_t t = 0; t < g.second.size(); t++) out[g.second[t]] = chars[t];
}
return out;
}JavaScript
var smallestStringWithSwaps = function(s, pairs) {
var n = s.length;
var parent = [];
for (var t = 0; t < n; t++) parent.push(t);
var find = function(x) {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
};
for (var p = 0; p < pairs.length; p++) {
var a = find(pairs[p][0]), b = find(pairs[p][1]);
if (a !== b) parent[a] = b;
}
var groups = {};
for (var i = 0; i < n; i++) {
var r = String(find(i));
if (groups[r] === undefined) groups[r] = [];
groups[r].push(i);
}
var out = s.split("");
var keys = Object.keys(groups);
for (var k = 0; k < keys.length; k++) {
var idx = groups[keys[k]];
var chars = [];
for (var m = 0; m < idx.length; m++) chars.push(s.charAt(idx[m]));
chars.sort();
for (var q = 0; q < idx.length; q++) out[idx[q]] = chars[q];
}
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets