Smallest String With Swaps

🎯

Smallest String With Swaps

mediumGRAPHAmazonGoogle

Imagine you have a string and a list of pairs of indices where you can swap characters any number of times. How can you rearrange the string to get the lexicographically smallest possible string?

💡 This problem involves grouping indices that can be swapped freely and then sorting characters within those groups. Beginners often struggle because it requires understanding how to model swaps as connected components and then manipulate those components efficiently.

📋

Problem Statement

Given a string s and an array of pairs of indices in the string, where each pair indicates that the characters at those indices can be swapped any number of times, return the lexicographically smallest string that can be obtained by performing zero or more swaps.

1 ≤ s.length ≤ 10^50 ≤ pairs.length ≤ 10^50 ≤ pairs[i][0], pairs[i][1] < s.lengths consists of lowercase English letters

💡

Example

Input"s = \"dcab\", pairs = [[0,3],[1,2]]"

Output"bacd"

Indices 0 and 3 can be swapped, and indices 1 and 2 can be swapped. Group 1: indices {0,3} with chars 'd' and 'b' can be rearranged to 'b' and 'd'. Group 2: indices {1,2} with chars 'c' and 'a' can be rearranged to 'a' and 'c'. The final string is "bacd".

• Empty pairs array → string remains unchanged
• Pairs that form one big connected component → entire string can be rearranged
• Pairs that form multiple disconnected components → sort each component independently
• String with all identical characters → output is same as input

⚠️

Common Mistakes

Not using union-find or graph traversal to group indices

Incorrect grouping leads to wrong character swaps and incorrect output

✅ Implement union-find or DFS to find connected components

Sorting characters but not sorting indices before assignment

Characters assigned to wrong positions, resulting in incorrect string

✅ Sort indices before assigning sorted characters back

Not applying path compression in union-find find()

Union-find operations become slow, causing timeouts

✅ Implement path compression in find() method

Modifying original string directly without copying

May cause unexpected behavior or errors in some languages

✅ Convert string to mutable array or char array before modifications

Not handling empty pairs array as a special case

Unnecessary processing or errors

✅ Check if pairs is empty and return original string early

🧠

Brute Force (Try All Swaps Recursively)

💡 This approach exists to understand the problem's combinatorial explosion and why naive attempts fail. It helps grasp the problem's complexity before optimizing.

Intuition

Try all possible swaps recursively and keep track of the lexicographically smallest string found.

Algorithm

1. Generate all possible strings by swapping pairs recursively.
2. Keep track of visited strings to avoid infinite loops.
3. Compare all generated strings to find the lexicographically smallest.
4. Return the smallest string found.

💡 The algorithm is hard because the number of possible strings grows exponentially, and managing visited states is tricky.

</>

Code

from typing import List

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        visited = set()
        res = s
        def dfs(arr):
            nonlocal res
            curr = ''.join(arr)
            if curr in visited:
                return
            visited.add(curr)
            if curr < res:
                res = curr
            for x, y in pairs:
                arr[x], arr[y] = arr[y], arr[x]
                dfs(arr)
                arr[x], arr[y] = arr[y], arr[x]
        dfs(list(s))
        return res

# Example usage:
if __name__ == '__main__':
    sol = Solution()
    print(sol.smallestStringWithSwaps("dcab", [[0,3],[1,2]]))  # Output: "bacd"

Line Notes

visited = set()Track visited strings to avoid infinite recursion

res = sInitialize result with original string

def dfs(arr):Define recursive function to explore swaps

if curr in visited:Skip already visited string states

if curr < res:Update result if current string is lex smaller

for x, y in pairs:Try swapping each pair

arr[x], arr[y] = arr[y], arr[x]Backtrack swap

dfs(arr)Recurse with swapped string

import java.util.*;

public class Solution {
    private String res;
    private Set<String> visited;
    private List<int[]> pairs;

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairsList) {
        this.res = s;
        this.visited = new HashSet<>();
        this.pairs = new ArrayList<>();
        for (List<Integer> p : pairsList) {
            this.pairs.add(new int[]{p.get(0), p.get(1)});
        }
        dfs(s.toCharArray());
        return res;
    }

    private void dfs(char[] arr) {
        String curr = new String(arr);
        if (visited.contains(curr)) return;
        visited.add(curr);
        if (curr.compareTo(res) < 0) res = curr;
        for (int[] p : pairs) {
            int x = p[0], y = p[1];
            char temp = arr[x]; arr[x] = arr[y]; arr[y] = temp;
            dfs(arr);
            temp = arr[x]; arr[x] = arr[y]; arr[y] = temp;
        }
    }

    // Example usage
    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> pairs = Arrays.asList(Arrays.asList(0,3), Arrays.asList(1,2));
        System.out.println(sol.smallestStringWithSwaps("dcab", pairs)); // Output: "bacd"
    }
}

Line Notes

private String res;Store current best lexicographically smallest string

private Set<String> visited;Track visited string states to avoid cycles

for (List<Integer> p : pairsList)Convert input pairs to int arrays for efficiency

String curr = new String(arr);Create string from char array for comparison

if (visited.contains(curr)) return;Skip already visited states

if (curr.compareTo(res) < 0) res = curr;Update result if current string is smaller

for (int[] p : pairs)Try swapping each pair

char temp = arr[x]; arr[x] = arr[y]; arr[y] = temp;Perform swap

dfs(arr);Recurse with swapped string

temp = arr[x]; arr[x] = arr[y]; arr[y] = temp;Backtrack swap

#include <bits/stdc++.h>
using namespace std;

class Solution {
    string res;
    unordered_set<string> visited;
    vector<pair<int,int>> pairs;
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairsVec) {
        res = s;
        for (auto &p : pairsVec) pairs.emplace_back(p[0], p[1]);
        dfs(s);
        return res;
    }

    void dfs(string &s) {
        if (visited.count(s)) return;
        visited.insert(s);
        if (s < res) res = s;
        for (auto &p : pairs) {
            swap(s[p.first], s[p.second]);
            dfs(s);
            swap(s[p.first], s[p.second]);
        }
    }
};

// Example usage
int main() {
    Solution sol;
    vector<vector<int>> pairs = {{0,3},{1,2}};
    cout << sol.smallestStringWithSwaps("dcab", pairs) << "\n"; // Output: "bacd"
    return 0;
}

Line Notes

string res;Store best lexicographically smallest string found

unordered_set<string> visited;Track visited strings to avoid infinite recursion

for (auto &p : pairsVec) pairs.emplace_back(p[0], p[1]);Convert input pairs to vector of pairs

if (visited.count(s)) return;Skip already visited string states

if (s < res) res = s;Update result if current string is smaller

for (auto &p : pairs)Try swapping each pair

swap(s[p.first], s[p.second]);Backtrack swap

dfs(s);Recurse with swapped string

var smallestStringWithSwaps = function(s, pairs) {
    let res = s;
    let visited = new Set();
    function dfs(arr) {
        let curr = arr.join('');
        if (visited.has(curr)) return;
        visited.add(curr);
        if (curr < res) res = curr;
        for (let [x, y] of pairs) {
            [arr[x], arr[y]] = [arr[y], arr[x]];
            dfs(arr);
            [arr[x], arr[y]] = [arr[y], arr[x]];
        }
    }
    dfs(s.split(''));
    return res;
};

// Example usage
console.log(smallestStringWithSwaps("dcab", [[0,3],[1,2]])); // Output: "bacd"

Line Notes

let res = s;Initialize result with original string

let visited = new Set();Track visited string states to avoid infinite loops

function dfs(arr) {Recursive function to explore all swaps

if (visited.has(curr)) return;Skip already visited states

if (curr < res) res = curr;Update result if current string is smaller

for (let [x, y] of pairs) {Try swapping each pair

[arr[x], arr[y]] = [arr[y], arr[x]];Backtrack swap

dfs(arr);Recurse with swapped string

⏱

Complexity

TimeO(n! * m) where n is string length and m is number of pairs

SpaceO(n! * n) due to visited states and recursion stack

Trying all permutations by swapping pairs leads to factorial time complexity, which is infeasible for large inputs.

💡 For n=10, factorial is 3,628,800, which is too large to compute in reasonable time.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem's complexity and motivates better solutions.

🧠

Union-Find to Group Indices + Sort Each Group

💡 This approach uses union-find to group indices that can be swapped freely, then sorts characters within each group to build the smallest string.

Intuition

Indices connected by pairs form connected components. Within each component, characters can be rearranged arbitrarily. So, group indices, collect their characters, sort them, and place back.

Algorithm

1. Initialize union-find structure for all indices.
2. Union indices connected by pairs.
3. Group indices by their root parent.
4. For each group, extract characters, sort them, and reassign to indices in sorted order.
5. Build and return the final string.

💡 The challenge is to correctly group indices and then sort characters within each group to achieve the lexicographically smallest string.

</>

Code

from typing import List

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[ry] < self.rank[rx]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        uf = UnionFind(n)
        for x, y in pairs:
            uf.union(x, y)
        groups = {}
        for i in range(n):
            root = uf.find(i)
            groups.setdefault(root, []).append(i)
        res = list(s)
        for indices in groups.values():
            chars = [res[i] for i in indices]
            chars.sort()
            for i, c in zip(sorted(indices), chars):
                res[i] = c
        return ''.join(res)

# Example usage
if __name__ == '__main__':
    sol = Solution()
    print(sol.smallestStringWithSwaps("dcab", [[0,3],[1,2]]))  # Output: "bacd"

Line Notes

self.parent = list(range(n))Initialize each node as its own parent

def find(self, x):Find root parent with path compression

if self.parent[x] != x:Compress path for efficiency

def union(self, x, y):Union two sets by rank

for x, y in pairs: uf.union(x, y)Union indices connected by pairs

groups.setdefault(root, []).append(i)Group indices by their root parent

chars.sort()Sort characters in each connected component

for i, c in zip(sorted(indices), chars):Assign sorted chars back to sorted indices

import java.util.*;

class UnionFind {
    int[] parent, rank;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
    }
}

public class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);
        for (List<Integer> p : pairs) uf.union(p.get(0), p.get(1));
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
        }
        char[] res = s.toCharArray();
        for (List<Integer> indices : groups.values()) {
            List<Character> chars = new ArrayList<>();
            for (int idx : indices) chars.add(res[idx]);
            Collections.sort(chars);
            Collections.sort(indices);
            for (int i = 0; i < indices.size(); i++) {
                res[indices.get(i)] = chars.get(i);
            }
        }
        return new String(res);
    }

    // Example usage
    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> pairs = Arrays.asList(Arrays.asList(0,3), Arrays.asList(1,2));
        System.out.println(sol.smallestStringWithSwaps("dcab", pairs)); // Output: "bacd"
    }
}

Line Notes

parent = new int[n];Initialize parent array for union-find

if (parent[x] != x) parent[x] = find(parent[x]);Path compression in find

int rx = find(x), ry = find(y);Find root parents before union

if (rank[rx] < rank[ry]) parent[rx] = ry;Attach smaller rank tree under bigger

groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);Group indices by root parent

char[] res = s.toCharArray();Convert string to char array for modification

Collections.sort(chars);Sort characters in each group

Collections.sort(indices);Sort indices to assign chars correctly

res[indices.get(i)] = chars.get(i);Assign sorted chars back to string

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n,0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
    }
};

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = (int)s.size();
        UnionFind uf(n);
        for (auto &p : pairs) uf.unite(p[0], p[1]);
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; i++) {
            groups[uf.find(i)].push_back(i);
        }
        string res = s;
        for (auto &kv : groups) {
            vector<int> &indices = kv.second;
            string chars;
            for (int i : indices) chars.push_back(res[i]);
            sort(chars.begin(), chars.end());
            sort(indices.begin(), indices.end());
            for (int i = 0; i < (int)indices.size(); i++) {
                res[indices[i]] = chars[i];
            }
        }
        return res;
    }
};

// Example usage
int main() {
    Solution sol;
    vector<vector<int>> pairs = {{0,3},{1,2}};
    cout << sol.smallestStringWithSwaps("dcab", pairs) << "\n"; // Output: "bacd"
    return 0;
}

Line Notes

iota(parent.begin(), parent.end(), 0);Initialize each node as its own parent

if (parent[x] != x) parent[x] = find(parent[x]);Path compression in find

int rx = find(x), ry = find(y);Find root parents before union

if (rank[rx] < rank[ry]) parent[rx] = ry;Attach smaller rank tree under bigger

groups[uf.find(i)].push_back(i);Group indices by root parent

string chars;Collect characters in each group

sort(chars.begin(), chars.end());Sort characters in group

sort(indices.begin(), indices.end());Sort indices to assign chars correctly

res[indices[i]] = chars[i];Assign sorted chars back to string

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    union(x, y) {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[ry] < this.rank[rx]) this.parent[ry] = rx;
        else {
            this.parent[ry] = rx;
            this.rank[rx]++;
        }
    }
}

var smallestStringWithSwaps = function(s, pairs) {
    const n = s.length;
    const uf = new UnionFind(n);
    for (const [x, y] of pairs) uf.union(x, y);
    const groups = new Map();
    for (let i = 0; i < n; i++) {
        const root = uf.find(i);
        if (!groups.has(root)) groups.set(root, []);
        groups.get(root).push(i);
    }
    const res = s.split('');
    for (const indices of groups.values()) {
        const chars = indices.map(i => res[i]);
        chars.sort();
        indices.sort((a,b) => a - b);
        for (let i = 0; i < indices.length; i++) {
            res[indices[i]] = chars[i];
        }
    }
    return res.join('');
};

// Example usage
console.log(smallestStringWithSwaps("dcab", [[0,3],[1,2]])); // Output: "bacd"

Line Notes

this.parent = Array.from({length: n}, (_, i) => i);Initialize each node as its own parent

if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); }Path compression in find

let rx = this.find(x), ry = this.find(y);Find root parents before union

if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;Attach smaller rank tree under bigger

groups.get(root).push(i);Group indices by root parent

const chars = indices.map(i => res[i]);Collect characters in each group

chars.sort();Sort characters in group

indices.sort((a,b) => a - b);Sort indices to assign chars correctly

res[indices[i]] = chars[i];Assign sorted chars back to string

⏱

Complexity

TimeO(n log n + m α(n)) where n is string length, m is pairs count, α is inverse Ackermann

SpaceO(n) for union-find and grouping

Union-find operations are almost O(1), grouping and sorting each connected component dominates with sorting cost.

💡 For n=10^5, sorting small groups is efficient, and union-find keeps grouping fast.

Interview Verdict: Accepted

This approach is efficient and optimal for the problem constraints and is the recommended solution in interviews.

🧠

Union-Find + Priority Queue for On-the-Fly Character Assignment

💡 This approach optimizes the previous by using priority queues (min-heaps) to assign characters on the fly, avoiding sorting after grouping.

Intuition

Instead of sorting characters after grouping, insert characters into min-heaps per group during grouping, then assign the smallest character available when reconstructing the string.

Algorithm

1. Initialize union-find for all indices.
2. Union indices connected by pairs.
3. Create a map from root parent to a min-heap of characters.
4. For each index, add its character to the min-heap of its group.
5. Reconstruct the string by polling the smallest character from each group's min-heap for each index.

💡 This approach is a variation that uses data structures to optimize character retrieval, but the core grouping idea remains the same.

</>

Code

from typing import List
import heapq

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[ry] < self.rank[rx]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        uf = UnionFind(n)
        for x, y in pairs:
            uf.union(x, y)
        groups = {}
        for i in range(n):
            root = uf.find(i)
            if root not in groups:
                groups[root] = []
            heapq.heappush(groups[root], s[i])
        res = []
        for i in range(n):
            root = uf.find(i)
            smallest_char = heapq.heappop(groups[root])
            res.append(smallest_char)
        return ''.join(res)

# Example usage
if __name__ == '__main__':
    sol = Solution()
    print(sol.smallestStringWithSwaps("dcab", [[0,3],[1,2]]))  # Output: "bacd"

Line Notes

heapq.heappush(groups[root], s[i])Add character to min-heap for its group

smallest_char = heapq.heappop(groups[root])Pop smallest character from group's min-heap

res.append(smallest_char)Build result string with smallest available chars

uf.union(x, y)Union indices connected by pairs

if root not in groups: groups[root] = []Initialize min-heap list for new group

import java.util.*;

class UnionFind {
    int[] parent, rank;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
    }
}

public class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);
        for (List<Integer> p : pairs) uf.union(p.get(0), p.get(1));
        Map<Integer, PriorityQueue<Character>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            groups.computeIfAbsent(root, k -> new PriorityQueue<>()).offer(s.charAt(i));
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            res.append(groups.get(root).poll());
        }
        return res.toString();
    }

    // Example usage
    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> pairs = Arrays.asList(Arrays.asList(0,3), Arrays.asList(1,2));
        System.out.println(sol.smallestStringWithSwaps("dcab", pairs)); // Output: "bacd"
    }
}

Line Notes

groups.computeIfAbsent(root, k -> new PriorityQueue<>()).offer(s.charAt(i));Add character to min-heap for its group

res.append(groups.get(root).poll());Poll smallest character from group's min-heap

uf.union(p.get(0), p.get(1));Union indices connected by pairs

new PriorityQueue<>()Priority queue to maintain sorted order of characters

int root = uf.find(i);Find root parent for grouping

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n,0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
    }
};

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = (int)s.size();
        UnionFind uf(n);
        for (auto &p : pairs) uf.unite(p[0], p[1]);
        unordered_map<int, priority_queue<char, vector<char>, greater<char>>> groups;
        for (int i = 0; i < n; i++) {
            groups[uf.find(i)].push(s[i]);
        }
        string res;
        res.reserve(n);
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            res.push_back(groups[root].top());
            groups[root].pop();
        }
        return res;
    }
};

// Example usage
int main() {
    Solution sol;
    vector<vector<int>> pairs = {{0,3},{1,2}};
    cout << sol.smallestStringWithSwaps("dcab", pairs) << "\n"; // Output: "bacd"
    return 0;
}

Line Notes

unordered_map<int, priority_queue<char, vector<char>, greater<char>>> groups;Map root to min-heap of characters

groups[uf.find(i)].push(s[i]);Push character into group's min-heap

res.push_back(groups[root].top());Append smallest character from min-heap

groups[root].pop();Remove used character from min-heap

uf.unite(p[0], p[1]);Union indices connected by pairs

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    union(x, y) {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[ry] < this.rank[rx]) this.parent[ry] = rx;
        else {
            this.parent[ry] = rx;
            this.rank[rx]++;
        }
    }
}

class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(val) {
        this.heap.push(val);
        this._siftUp();
    }
    pop() {
        if (this.heap.length === 0) return null;
        const top = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this._siftDown();
        }
        return top;
    }
    _siftUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent] <= this.heap[idx]) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    _siftDown() {
        let idx = 0;
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1, right = 2 * idx + 2, smallest = idx;
            if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
            if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
            if (smallest === idx) break;
            [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
            idx = smallest;
        }
    }
}

var smallestStringWithSwaps = function(s, pairs) {
    const n = s.length;
    const uf = new UnionFind(n);
    for (const [x, y] of pairs) uf.union(x, y);
    const groups = new Map();
    for (let i = 0; i < n; i++) {
        const root = uf.find(i);
        if (!groups.has(root)) groups.set(root, new MinHeap());
        groups.get(root).push(s[i]);
    }
    const res = [];
    for (let i = 0; i < n; i++) {
        const root = uf.find(i);
        res.push(groups.get(root).pop());
    }
    return res.join('');
};

// Example usage
console.log(smallestStringWithSwaps("dcab", [[0,3],[1,2]])); // Output: "bacd"

Line Notes

this.parent = Array.from({length: n}, (_, i) => i);Initialize each node as its own parent

if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); }Path compression in find

let rx = this.find(x), ry = this.find(y);Find root parents before union

groups.set(root, new MinHeap());Initialize min-heap for new group

groups.get(root).push(s[i]);Push character into group's min-heap

res.push(groups.get(root).pop());Pop smallest character from min-heap for result

uf.union(x, y);Union indices connected by pairs

⏱

Complexity

TimeO(n log n + m α(n)) similar to previous approach

SpaceO(n) for union-find and heaps

Using heaps avoids explicit sorting but still requires O(log n) per insertion and extraction, overall similar complexity.

💡 This approach is a practical optimization but conceptually similar to sorting groups.

Interview Verdict: Accepted

This approach is an optimization variant and is acceptable in interviews if explained well.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always implement the union-find grouping + sorting approach (Approach 2) as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * m)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Union-Find + Sort Each Group	O(n log n + m α(n))	O(n)	No	Yes	Code this approach
3. Union-Find + Priority Queue	O(n log n + m α(n))	O(n)	No	Yes	Optional optimization to mention

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, and finally present the optimal union-find approach.

How to Present

Clarify the problem and constraints.Describe the brute force approach and why it is inefficient.Introduce union-find to group indices that can be swapped.Explain sorting characters within each group to get the smallest string.Optionally mention priority queue optimization.Write clean, modular code and test with examples.

Time Allocation

Clarify: 3min → Approach: 7min → Code: 10min → Test & Optimize: 5min. Total ~25min

What the Interviewer Tests

Understanding of union-find data structure, ability to model swaps as connected components, and skill in sorting and reconstructing the string efficiently.

Common Follow-ups

• What if pairs are very large? → Use union-find for efficient grouping.
• Can you do it without sorting? → Use priority queues for on-the-fly smallest character retrieval.

💡 These follow-ups test your knowledge of data structures and optimization techniques beyond the basic solution.

🔍

Pattern Recognition

When to Use

1) Problem involves swapping characters or elements at given pairs of indices. 2) Swaps can be performed any number of times. 3) Goal is to find lexicographically smallest or largest arrangement. 4) Need to group indices that can be swapped freely.

Signature Phrases

"You can swap characters at these pairs any number of times""Return the lexicographically smallest string after swaps"

NOT This Pattern When

Problems that require only one swap or fixed swaps without grouping are different patterns.

Similar Problems

Accounts Merge - uses union-find to group accountsNumber of Connected Components in an Undirected Graph - find connected componentsEvaluate Division - union-find with weighted edges

Practice

1. You are given a list of user accounts, each with a username and multiple email addresses. Some accounts may belong to the same user if they share at least one email address. Which algorithmic approach best guarantees merging all accounts belonging to the same user efficiently?

easy

A. Greedy approach that merges accounts by comparing usernames only

B. Dynamic programming to find the longest common subsequence of emails

C. Brute force nested loops checking every pair of accounts for email overlap

D. Union-Find data structure to group emails that appear in multiple accounts

Solution

1. Step 1: Understand the problem structure

   The problem requires grouping accounts by shared emails, which naturally forms connected components in a graph where emails are nodes.

2. Step 2: Identify the suitable algorithm

   Union-Find efficiently merges sets of emails that belong to the same user, handling multiple overlaps without redundant comparisons.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Union-Find is the classic pattern for merging overlapping sets [OK]

Hint: Accounts merge is a connected components problem [OK]

Common Mistakes:

• Merging by username only misses shared emails
• Brute force is too slow for large inputs

2. Consider the following Python code implementing Kruskal's MST with union by size and path compression. Given the input graph with edges [(0,1,1), (1,2,2), (0,2,3)] and n=3, what is the value of mst_weight after processing all edges?

easy

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Sort edges by weight

   Edges sorted: (0,1,1), (1,2,2), (0,2,3)

2. Step 2: Process edges and union sets

   Union(0,1) succeeds, mst_weight=1; Union(1,2) succeeds, mst_weight=3; Union(0,2) fails (already connected).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of edges in MST is 1+2=3 [OK]

Hint: Sum weights of first n-1 edges that connect components [OK]

Common Mistakes:

• Adding all edges regardless of cycle
• Off-by-one in edges_used count
• Misordering edges before union

3. What is the time complexity of Kruskal's algorithm using union-find with path compression and union by size on a graph with n vertices and m edges?

medium

A. O(m log m + m α(n))

B. O(n^2)

C. O(m n)

D. O(m log n)

Solution

1. Step 1: Identify sorting cost

   Sorting edges takes O(m log m) time, which is equivalent to O(m log n) since m ≤ n^2.

2. Step 2: Analyze union-find operations

   Union-find operations take O(m α(n)) where α(n) is inverse Ackermann function, almost constant.

3. Step 3: Combine complexities

   The total complexity is O(m log n) dominated by sorting, as α(n) is negligible.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Sorting dominates, union-find nearly linear [OK]

Hint: Sorting edges + near-linear union-find cost dominates [OK]

Common Mistakes:

• Confusing α(n) with log n or n
• Assuming union-find is O(n) per operation
• Ignoring sorting cost or assuming O(m log n)

4. Examine the following buggy Union-Find code snippet for the network connectivity problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line with 'return self.find(self.parent[x])' in find method

B. Line 'self.count = n' in __init__ method

C. Line 'self.rank[rootX] += 1' in union method

D. Line 'self.parent[rootX] = rootY' in union method

Solution

1. Step 1: Identify path compression implementation

   The find method should assign the parent during recursion: self.parent[x] = self.find(self.parent[x]) to flatten the tree.

2. Step 2: Understand impact of missing assignment

   Without path compression, find operations become slower and can cause TLE or incorrect component counts on large inputs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing path compression assignment is a classic subtle bug [OK]

Hint: Path compression requires assignment to parent during find [OK]

Common Mistakes:

• Forgetting path compression assignment
• Misplacing rank increment
• Incorrectly decrementing count

5. Examine the following buggy code snippet for the optimal solution. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 2: Sorting edges by type descending

B. Line 16: Checking if both Alice and Bob are fully connected

C. Line 9: Using union-find union for type 3 edges

D. Line 6: Not adjusting node indices from 1-based to 0-based

Solution

1. Step 1: Identify indexing issue

   Input edges use 1-based node indices, but union-find expects 0-based. Missing adjustment causes wrong unions or runtime errors.

2. Step 2: Confirm other lines are correct

   Sorting edges, union calls, and connectivity checks are correct; only indexing is buggy.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing "u -= 1; v -= 1" causes incorrect unions [OK]

Hint: Check if node indices are adjusted before union-find calls [OK]

Common Mistakes:

• Ignoring 1-based to 0-based index conversion
• Misusing union-find union return value
• Skipping connectivity check for both users