Log inSign up
mediumleetcodeNot Started

Smallest String With Swaps

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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 that can be swapped.

All pairs are 0-indexed.

You can swap the characters at any pair of indices in pairs any number of times.

Return the *lexicographically smallest string that s can be changed to after using the swaps*.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explanation: Swap s[0] and s[3], s becomes "bcad". Swap s[1] and s[2], s becomes "bacd".

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explanation: Indices {0, 2, 3} are connected, so their characters can be sorted as "acd" at indices [0, 2, 3]. Index 1 has "b". Final string is "abcd".

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explanation: All indices {0, 1, 2} are connected. Sorting characters "cba" gives "abc".

Constraints:

  • 1 <= s.length <= 105
  • 0 <= pairs.length <= 105
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s only contains lower case English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model transitive swap operations as graph connected components.
  • Implement Disjoint Set Union with path compression and union by rank.
  • Sort and reassign component characters in O(V log V) time.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Arbitrary number of swaps across given index pairs.
  • Finding the lexicographically smallest/largest arrangement achievable through transitive exchanges.

Algorithmic Decision Tree:

  • Arbitrary number of swaps across given index pairs.
  • Finding the lexicographically smallest/largest arrangement achievable through transitive exchanges.

Connected Patterns:

Accounts MergeRedundant ConnectionEvaluate Division

1. DFS Connected Components Traversal

Intuition

Build an undirected graph where edges are the swap pairs. Maintain a visited array. For each unvisited index i, perform DFS to collect all indices in its connected component. Extract the characters at these indices, sort the indices and characters, and assign the sorted characters into the sorted indices.

When to apply: Basic graph search approach without DSU.

Algorithm

  1. Build adjacency list adj from pairs.
  2. Initialize visited array of size n with false.
  3. For i from 0 to n - 1:
  4. If !visited[i]:
  5. Run DFS collecting all connected indices.
  6. Extract chars = [s[idx] for idx in indices].
  7. Sort indices and sort chars.
  8. Assign res[indices[k]] = chars[k].
  9. Return res.

DFS Connected Components Traversal

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [d, c, a, b]
Current operationSTEP 1 OF 6
Observation: Swapping is transitive: if $a$ swaps with $b$ and $b$ with $c$, any permutation of ${a, b, c}$ can be achieved
Visual state
Values and pointers at this exact step
array
S
d
c
a
b
0
↑ PAIR [0, 3]
1
2
3
↑ SWAPPABLE
Variables at this step
graph
{"0":[3],"1":[2],"2":[1],"3":[0]}
Check / comparison
Build graph from pairs: edge (0, 3) connects indices 0 and 3. Edge (1, 2) connects 1 and 2.
Decision / next transition
DFS traverses swappable index graph to identify disjoint equivalence components.
Why this step matters

Observation: Swapping is transitive: if a swaps with b and b with c, any permutation of {a, b, c} can be achieved.

Decision: Model indices as an undirected graph. Find connected components using DFS.

Invariant: All indices within a connected component can freely reorder their characters.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7 void dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited, std::vector<int>& indices, std::string& chars, const std::string& s) {
8 visited[u] = true;
9 indices.push_back(u);
10 chars.push_back(s[u]);
11 for (int v : adj[u]) {
12 if (!visited[v]) {
13 dfs(v, adj, visited, indices, chars, s);
14 }
15 }
16 }
17public:
18 std::string smallestStringWithSwaps(std::string s, std::vector<std::vector<int>>& pairs) {
19 int n = s.size();
20 std::vector<std::vector<int>> adj(n);
21 for (const auto& p : pairs) {
22 adj[p[0]].push_back(p[1]);
23 adj[p[1]].push_back(p[0]);
24 }
25
26 std::vector<bool> visited(n, false);
27 std::string res = s;
28
29 for (int i = 0; i < n; ++i) {
30 if (!visited[i]) {
31 std::vector<int> indices;
32 std::string chars = "";
33 dfs(i, adj, visited, indices, chars, s);
34
35 std::sort(indices.begin(), indices.end());
36 std::sort(chars.begin(), chars.end());
37
38 for (size_t k = 0; k < indices.size(); ++k) {
39 res[indices[k]] = chars[k];
40 }
41 }
42 }
43 return res;
44 }
45};
46
47int main() {
48 Solution sol;
49 std::vector<std::vector<int>> pairs = {{0,3},{1,2}};
50 std::cout << sol.smallestStringWithSwaps("dcab", pairs) << std::endl; // "bacd"
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(V + E + V log V) — Graph traversal visits all V vertices and E edges once; sorting component characters takes O(V log V).
  • Space complexity: O(V + E) for adjacency list

Why Brute Force Doesn't Scale:

Using counting sort with 26 buckets sorts each component in linear O(K) time.

Disjoint Set Union uses compact 1D integer arrays.

2. Disjoint Set Union with Max-Heaps

Intuition

Union all pairs using DSU. For each index i, find its root parent = find(i) and push s[i] into a Min-Heap stored in map[parent]. In a second pass from 0 to n - 1, assign res[i] = map[find(i)].pop().

When to apply: When streaming characters back without sorting index arrays.

Algorithm

  1. Initialize DSU of size n.
  2. Union each pair [u, v].
  3. For i from 0 to n - 1: push s[i] into minHeapMap[find(i)].
  4. For i from 0 to n - 1: res[i] = minHeapMap[find(i)].popMin().
  5. Return res.

Disjoint Set Union with Max-Heaps

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [d, c, a, b]
Current operationSTEP 1 OF 6
Observation: Disjoint Set Union with path compression connects indices
Visual state
Values and pointers at this exact step
array
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
d
c
a
b
0
↑ DSU INIT: parent[i]=i
1
2
3
Binary Heap Tree Topology
d#0
c#1
a#2
b#3
Variables at this step
parent
[0,1,1,0]
Check / comparison
Initialize DSU: parent = [0, 1, 2, 3].
Decision / next transition
Union pairs: union(0, 3) -> parent[3]=0. union(1, 2) -> parent[2]=1.
Why this step matters

Observation: Disjoint Set Union with path compression connects indices.

Decision: Process pairs: (0, 3) creates set with root 0; (1, 2) creates set with root 1.

Invariant: Connected elements share an identical find(i) root representative.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <queue>
5#include <unordered_map>
6
7class DSU {
8public:
9 std::vector<int> parent;
10 DSU(int n) : parent(n) {
11 for (int i = 0; i < n; ++i) parent[i] = i;
12 }
13 int find(int i) {
14 if (parent[i] == i) return i;
15 return parent[i] = find(parent[i]);
16 }
17 void unite(int i, int j) {
18 int rootI = find(i), rootJ = find(j);
19 if (rootI != rootJ) parent[rootI] = rootJ;
20 }
21};
22
23class Solution {
24public:
25 std::string smallestStringWithSwaps(std::string s, std::vector<std::vector<int>>& pairs) {
26 int n = s.size();
27 DSU dsu(n);
28 for (const auto& p : pairs) {
29 dsu.unite(p[0], p[1]);
30 }
31
32 std::unordered_map<int, std::priority_queue<char, std::vector<char>, std::greater<char>>> heapMap;
33 for (int i = 0; i < n; ++i) {
34 heapMap[dsu.find(i)].push(s[i]);
35 }
36
37 std::string res = s;
38 for (int i = 0; i < n; ++i) {
39 int root = dsu.find(i);
40 res[i] = heapMap[root].top();
41 heapMap[root].pop();
42 }
43 return res;
44 }
45};
46
47int main() {
48 Solution sol;
49 std::vector<std::vector<int>> pairs = {{0,3},{1,2},{0,2}};
50 std::cout << sol.smallestStringWithSwaps("dcab", pairs) << std::endl; // "abcd"
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O((V + E) * α(V) + V log V) — DSU operations are near-linear; heap push/pops take O(V log V).
  • Space complexity: O(V)

3. Disjoint Set Union with Component Bucket Sorting (Optimal)

Intuition

Initialize DSU of size N. Union all swap pairs. Group all indices belonging to the same root. For each component, count the frequency of each character (26-size bucket). Iterate through the component's sorted indices and write the smallest available characters from the counting bucket. This runs in strict O(N * alpha(N)) time.

When to apply: The standard optimal solution combining Disjoint Set Union with counting sort.

Algorithm

  1. Initialize DSU(n) with rank and parent arrays.
  2. Union all pairs (u, v).
  3. Group indices by their DSU root: components[find(i)].push(i).
  4. For each component index list:
  5. Count character frequencies in count[26] for these indices.
  6. Iterate indices and populate with lowest alphabetical character from count.
  7. Return the resulting string.

Disjoint Set Connected Component Lexicographical Sorting

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [d, c, a, b]
Current operationSTEP 1 OF 6
Observation: First pair [0, 3] allows swapping indices 0 and 3
Visual state
Values and pointers at this exact step
array
S
d
c
a
b
0
↑ idx 0 ('d')
1
2
3
↑ idx 3 ('b')
Variables at this step
pair
[0,3]
union
0 <-> 3
rootMap
{"0":0,"1":1,"2":2,"3":0}
Why this step matters

Observation: First pair [0, 3] allows swapping indices 0 and 3.

Decision: Union indices 0 and 3 into component with root 0.

Invariant: Any indices in the same connected component can be freely rearranged.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <numeric>
5
6class DSU {
7public:
8 std::vector<int> parent, rank;
9 DSU(int n) : parent(n), rank(n, 0) {
10 std::iota(parent.begin(), parent.end(), 0);
11 }
12 int find(int i) {
13 if (parent[i] == i) return i;
14 return parent[i] = find(parent[i]);
15 }
16 void unite(int i, int j) {
17 int rootI = find(i), rootJ = find(j);
18 if (rootI != rootJ) {
19 if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
20 parent[rootJ] = rootI;
21 if (rank[rootI] == rank[rootJ]) rank[rootI]++;
22 }
23 }
24};
25
26class Solution {
27public:
28 std::string smallestStringWithSwaps(std::string s, std::vector<std::vector<int>>& pairs) {
29 int n = s.size();
30 DSU dsu(n);
31 for (const auto& p : pairs) {
32 dsu.unite(p[0], p[1]);
33 }
34
35 std::vector<std::vector<int>> components(n);
36 for (int i = 0; i < n; ++i) {
37 components[dsu.find(i)].push_back(i);
38 }
39
40 std::string res = s;
41 for (int root = 0; root < n; ++root) {
42 if (components[root].empty()) continue;
43
44 int count[26] = {0};
45 for (int idx : components[root]) {
46 count[s[idx] - 'a']++;
47 }
48
49 int charIdx = 0;
50 for (int idx : components[root]) {
51 while (count[charIdx] == 0) charIdx++;
52 res[idx] = 'a' + charIdx;
53 count[charIdx]--;
54 }
55 }
56 return res;
57 }
58};
59
60int main() {
61 Solution sol;
62 std::vector<std::vector<int>> pairs = {{0,3},{1,2},{0,2}};
63 std::cout << sol.smallestStringWithSwaps("dcab", pairs) << std::endl; // "abcd"
64 return 0;
65}

Time & Space Complexity

  • Time complexity: O((N + P) * α(N) + 26 * N) = O((N + P) * α(N)) — DSU union-find is inverse Ackermann time, and counting sort runs in O(N) over 26 lowercase characters.
  • Space complexity: O(N) for DSU and component lists

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS / BFS Connected ComponentsO(V + E + V log V)O(V + E) adjacency listStandard graph traversal without custom DSU class.Requires building full adjacency list and recursive call stack.
2.Disjoint Set Union (DSU) (Optimal)OptimalO((E + V) * α(V) + V log V)O(V) strictlyCompact memory, fast union-find with path compression, industry standard.Requires DSU boilerplate.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Assuming swaps are only between immediate neighbor pairs instead of transitive equivalence classes.

Pitfall 2:

Using O(V2) pairwise union-find without path compression.

Crucial Edge Cases to Validate:

  • Empty pairs list (pairs = []): No swaps possible, returns original string s.
  • All indices connected into a single component: Entire string sorted alphabetically in place.
  • Single character string: Returns s immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State that swap transitivity forms equivalence classes, making DSU or BFS the natural choice.
  2. Mention counting sort over 26 letters to achieve linear time per component.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can any set of characters within a connected component be sorted into any arbitrary permutation?

Back to DSA Sheet