leetcode 1202. Smallest String With Swaps

Seawolf

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.

 

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"
Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

 

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.

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int len = s.length();
        UnionFind u = new UnionFind(len);
        for(List <Integer> list: pairs){
            u.union(list.get(0),list.get(1));
        }
        
        Map <Integer, List<Character>> map = new HashMap<>();
        for(int i = 0; i <len; i++){
            int head = u.find(i);
            List<Character> cha = map.computeIfAbsent(head, k -> new ArrayList<>());
            cha.add(s.charAt(i));
        }
        
        for(List<Character> c : map.values()){
            Collections.sort(c);
        }
        
        StringBuilder re = new StringBuilder();
        Map <Integer,Integer> help = new HashMap<>();
        for(int i = 0 ; i< len; i++){
            
            int x =u.find(i);
            List<Character> list = map.get(x);
            help.put(x, help.getOrDefault(x,-1)+1);
            char aa = list.get(help.get(x));
            re.append(aa);
        }
        return re.toString();
    }
    
    public class UnionFind{
        
        int[] parent;
        int[] size;
        
        public UnionFind(int x){
            parent = new int[x];
            size = new int[x];
            for(int i = 0; i < x ; i++){
                size[i] = 1;
                parent[i] = i;
            }
            
        }
        
        public int find(int x){
            int root = x;
            while(root != parent[root]){
                
                parent[root] = parent[parent[root]];
                root = parent[root];
            }
            return root;
        }
        
        public int union(int x, int y){
            int rootx = find(x);
            int rooty = find(y);
            
            if(rootx == rooty){
                return size[rootx];
            }
            
            if(size[rootx] > size[rooty]){
                parent[rooty] = rootx;
                size[rootx] = size[rootx] + size[rooty];
                return size[rootx];
            }
            else if(size[rootx] < size[rooty]){
                parent[rootx] = rooty;
                size[rooty] = size[rooty] + size[rootx];
                return size[rooty];
            }
            else{
                parent[rootx] = rooty;
                size[rooty] = size[rooty] + size[rootx];
                return size[rooty];
            }
        }
    }
}