# 1202. Smallest String With Swaps
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/smallest-string-with-swaps/
## 思路
将可以互换的几个index放在一起，然后将他们按字母顺序排列
再遍历一遍字串，找到它对应的union，每次从中拿最小的一个就可以产生最后的答案
注意char array转换成string 不能直接像StringBuilder一样用```toString()```而是要用```String.valueOf()```
## Code

class Solution {
    int[] fa;
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        fa = new int[n];
        for(int i=0; i<n; i++){
            fa[i] = i;
        }
        for(List<Integer> pair:pairs){
            combine(pair.get(0), pair.get(1));
        }
        
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<n; i++){
            int f = find(i);
            if(!map.containsKey(f)) map.put(f, new ArrayList<>());
            map.get(f).add(i);
        }
        
        char[] ans = new char[n];
        for(List<Integer> index:map.values()){
            List<Integer> sortedIdx = new ArrayList<>(index);
            Collections.sort(sortedIdx, (a,b)->(s.charAt(a)-s.charAt(b)));
            for(int i=0; i<index.size(); i++){
                ans[index.get(i)] = s.charAt(sortedIdx.get(i));
            }
        }
        return String.valueOf(ans);
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[a] = b;
    }
}