1202.SmallestStringWithSwaps.java

class Solution {
    int[] parent;
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        
        parent = new int[s.length()];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        
        // detect connected components
        for (List<Integer> pair: pairs) {
            union(pair.get(0), pair.get(1));
        }
        
        // Sort characters of connected component at each position
        Map<Integer, PriorityQueue<Character>> map = new HashMap<Integer, PriorityQueue<Character>>();
        
        for (int i = 0; i < s.length(); i++) {
            int root = find(i);
            
            // Build a sorted list of characters from connection component at each position
            map.putIfAbsent(root, new PriorityQueue<Character>());
            map.get(root).offer(s.charAt(i));
        }
                
        StringBuilder sb = new StringBuilder();
        
        // Build the answer with smallest char at each position
        for (int i = 0; i < s.length(); i++) {
            sb.append(map.get(parent[i]).poll());
        }
        
        return sb.toString();
    }
    
    private int find(int a) {
        while (parent[a] != a) {
            parent[a] = parent[parent[a]];
            a = parent[a];
        }
        return a;
    }
    
    private void union(int a, int b) {
        int parentA = find(a);
        int parentB = find(b);
        
        if (parentA < parentB) {
            parent[parentB] = parentA;
        } else {
            parent[parentA] = parentB;
        }
    }
}