Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- int root[];
- int rank[];
- int find(int x) {
- if(x == root[x]) return x;
- return root[x] = find(root[x]);
- }
- void union(int x, int y) {
- int rootX = find(x);
- int rootY = find(y);
- if(rootX != rootY) {
- if(rank[rootX] > rank[rootY]) {
- root[rootY] = root[rootX];
- } else if(rank[rootX] < rank[rootY]) {
- root[rootX] = root[rootY];
- } else {
- root[rootY] = root[rootX];
- rank[rootX] += 1;
- }
- }
- }
- public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
- root = new int[s.length() + 7];
- rank = new int[s.length() + 7];
- for(int i=0; i<root.length; i++) {
- root[i] = i;
- rank[i] = 1;
- }
- for(List<Integer> pair : pairs) {
- union(pair.get(0), pair.get(1));
- }
- Map<Integer, List<Character>> charMap = new HashMap<>();
- for(int i=0; i<s.length(); i++) {
- int rootI = find(i);
- if(charMap.containsKey(rootI)) {
- charMap.get(rootI).add(s.charAt(i));
- } else {
- charMap.put(rootI, new ArrayList<>(List.of(s.charAt(i))));
- }
- }
- for(Integer key : charMap.keySet()) {
- Collections.sort(charMap.get(key));
- }
- String ans = "";
- for(int i=0; i<s.length(); i++) {
- ans += charMap.get(find(i)).get(0);
- charMap.get(find(i)).remove(0);
- }
- return ans;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement