1202. Smallest String With Swaps

tags: leetcode,priorityQueue,medium

ref: https://leetcode.com/problems/smallest-string-with-swaps/

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.

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

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

Constraints:
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

1. timeResolution:O(N) loop all space O(N)
2. 分組後排序 利用int[] 進行組紀錄
3. find 進行組查找
4. priorityQueue 進行同組排序

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        
        
        int[] group = new int[s.length()];
        for(int i=0;i<group.length;i++){
            group[i]=i;
        }
        
        for(int i=0;i<pairs.size();i++){

            int b1=find(group,pairs.get(i).get(0));
            int b2=find(group,pairs.get(i).get(1));
            
            int connect=Math.min(b1,b2);
            group[b1]=connect;
            group[b2]=connect;
        }
        
        Map<Integer,PriorityQueue<Character>> pile = new HashMap<>();
        
        for(int i=0;i<group.length;i++){
            
            int base=find(group,i);

            if(!pile.containsKey(base)){
                pile.put(base,new PriorityQueue<Character>());
            }
            pile.get(base).add(s.charAt(i));
        }
        
        StringBuilder ans=new StringBuilder();
        
        for(int base:group){
            ans.append(pile.get(base).poll());
        }
        
        
        return ans.toString();
    }
    
    
    private int find(int[] arr, int idx){

        while(arr[idx]!=idx){
            arr[idx]=arr[arr[idx]];
            idx=arr[idx];
        }
        return arr[idx];
    }