Smallest String With Swaps

Given a string s and pairs of indices, you can swap any pair any number of times. Return the lexicographically smallest string possible.

Example 1

Input: s="dcab", pairs=[[0,3],[1,2]] → Output: "bacd"

Example 2

Input: s="dcab", pairs=[[0,3],[1,2],[0,2]] → Output: "abcd"

Solution Approach

Union-Find: connected components of indices can be freely permuted. Sort each component and place characters in sorted order.

Union-Find on indices 0..n-1.
Group indices by their root (use Map>).
For each group: sort the characters, sort the indices.
Assign sorted chars to sorted indices.

Java

import java.util.*;

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

Time Complexity: O(N log N + E * alpha(N))
Space Complexity: O(N)