Advertisement
Guest User

Untitled

a guest
Mar 15th, 2022
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    
  3.     int root[];
  4.     int rank[];
  5.    
  6.     int find(int x) {
  7.         if(x == root[x]) return x;
  8.         return root[x] = find(root[x]);
  9.     }
  10.    
  11.     void union(int x, int y) {
  12.         int rootX = find(x);
  13.         int rootY = find(y);
  14.         if(rootX != rootY) {
  15.             if(rank[rootX] > rank[rootY]) {
  16.                 root[rootY] = root[rootX];
  17.             } else if(rank[rootX] < rank[rootY]) {
  18.                 root[rootX] = root[rootY];
  19.             } else {
  20.                 root[rootY] = root[rootX];
  21.                 rank[rootX] += 1;
  22.             }
  23.         }
  24.     }
  25.    
  26.     public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
  27.         root = new int[s.length() + 7];
  28.         rank = new int[s.length() + 7];
  29.         for(int i=0; i<root.length; i++) {
  30.             root[i] = i;
  31.             rank[i] = 1;
  32.         }
  33.        
  34.         for(List<Integer> pair : pairs) {
  35.             union(pair.get(0), pair.get(1));
  36.         }
  37.        
  38.         Map<Integer, List<Character>> charMap = new HashMap<>();
  39.         for(int i=0; i<s.length(); i++) {
  40.             int rootI = find(i);
  41.             if(charMap.containsKey(rootI)) {
  42.                 charMap.get(rootI).add(s.charAt(i));
  43.             } else {
  44.                 charMap.put(rootI, new ArrayList<>(List.of(s.charAt(i))));  
  45.             }
  46.         }
  47.        
  48.         for(Integer key : charMap.keySet()) {
  49.             Collections.sort(charMap.get(key));
  50.         }
  51.        
  52.         String ans = "";
  53.         for(int i=0; i<s.length(); i++) {
  54.             ans += charMap.get(find(i)).get(0);
  55.             charMap.get(find(i)).remove(0);
  56.         }
  57.         return ans;
  58.        
  59.     }
  60. }
Advertisement
RAW Paste Data Copied
Advertisement