You are given a string s, and an array of pairs of indices in the string&nbsp;pairs&nbsp;where&nbsp;pairs[i] =&nbsp;[a, b]&nbsp;indicates 2 indices(0-indexed) of the string.

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

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

&nbsp;
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"


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 10^5
	0 &lt;= pairs.length &lt;= 10^5
	0 &lt;= pairs[i][0], pairs[i][1] &lt;&nbsp;s.length
	s&nbsp;only contains lower case English letters.


class DSU:
    def __init__(self):
        self.parentof = [-1 for _ in range(100001)]
        self.rankof = [1 for _ in range(100001)]

    def find(self,ele):
        def recur(ele):
            if self.parentof[ele]==-1: 
                return ele
            par = recur(self.parentof[ele])
            self.parentof[ele] = par
            return par
        return recur(ele)

    def unify(self,ele1,ele2):
        p1,p2 = self.find(ele1),self.find(ele2)
        r1,r2 = self.rankof[p1],self.rankof[p2]

        if p1==p2: return 
        if r1>r2:
            self.parentof[p2] = p1
        else:
            self.parentof[p1]=p2
            if r1==r2: self.rankof[p2]+=1

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        dsu = DSU()
        nodes = set()
        smallest = [s[i] for i in range(len(s))]

        for i,j in pairs:
            dsu.unify(i,j)
            nodes.add(i)
            nodes.add(j)

        groups = {}
        for node in nodes:
            par = dsu.find(node)
            if par not in groups:
                groups[par] = [node]
            else:
                groups[par].append(node)
        
        for group in groups.values():
            letters,k = sorted([s[i] for i in group]),0
            
            for i in group:
                smallest[i] = letters[k]
                k+=1

        return "".join(smallest)
class Solution {
    int[]parent;
    int[]rank;
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        parent = new int[s.length()];
        rank = new int[s.length()];
        for(int i=0;i<parent.length;i++){
            parent[i] = i;
            rank[i] = 0;
        }
        
        //Union of All Pairs who belongs to same set
        for(List<Integer> l : pairs){
            int i = l.get(0);
            int j = l.get(1);
            
            int il = find(i);
            int jl = find(j);
            if(il != jl){
                union(il,jl);
            }
        }
        
        //To get the Character in sorted order
        PriorityQueue<Character>[]pq = new PriorityQueue[s.length()];
        for(int i=0;i<pq.length;i++){
            pq[i] = new PriorityQueue<>();
        }
        
        for(int i=0;i<s.length();i++){
            int il = find(i);
            char ch = s.charAt(i);
            pq[il].add(ch);
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++){
            int il = find(i);
            char ch = pq[il].remove();
            sb.append(ch);
        }
        
        return sb.toString();
    }
    
    
    int find(int x){
        if(parent[x] == x){
            return x;
        }else{
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }
    void union(int x,int y){
        if(rank[x] < rank[y]){
            parent[x] = y;
        }else if(rank[y] < rank[x]){
            parent[y] = x;
        }else{
            parent[x] = y;
            rank[y]++;
        }
    }
}
class Solution {
public:

    vector<int> parent;

    int findParent(int n)
    {
        if(parent[n] == n) return n;
        return parent[n] = findParent(parent[n]);
    }

    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs)
    {
        map<int, set<int>> mp;
        parent.resize(s.size());
        string ans = s;

        for(int i=0; i<s.length(); i++) parent[i] = i;

        for(auto pair: pairs)
        {
            int p1 = findParent(pair[0]), p2 = findParent(pair[1]);
            if(p1 != p2) parent[p2] = p1;
        }

        for(auto pair: pairs)
        {
            int p = findParent(pair[0]);
            mp[p].insert(pair[0]);
            mp[p].insert(pair[1]);
        }

        for(auto it: mp)
        {
            vector<char> part;
            set<int> idx = it.second;

            for(auto index: idx) part.push_back(s[index]);

            sort(part.begin(), part.end());

            auto index = idx.begin();
            for(auto x: part) ans[*index] = x, ++index;
        }

        return ans;
    }
};
var smallestStringWithSwaps = function(s, pairs) {
    const uf = new UnionFind(s.length);
    pairs.forEach(([x,y]) => uf.union(x,y))
    
    const result = [];
    for (const [root, charIndex] of Object.entries(uf.disjointSets())) {
      let chars = charIndex.map(i => s[i])
      chars.sort();
      charIndex.forEach((charIndex, i) => result[charIndex] = chars[i])
    }
    
    return result.join("")
};

class UnionFind {
    constructor(len) {
      this.roots = Array.from({length: len}).map((_, i) => i);
      this.rank = Array.from({length: len}).fill(1);
    }
    
    find(x) { 
      if (x == this.roots[x]) {
        return x;
       }
      return this.roots[x] = this.find(this.roots[x])
    }
    
    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        
      if (this.rank[rootX] > this.rank[rootY]) {
        this.roots[rootY] = rootX;
       } else if (this.rank[rootX] < this.rank[rootY]) {
           this.roots[rootX] = rootY;
       } else { // ranks equal
           this.roots[rootY] = rootX;
           this.rank[rootX]++
       }
    }
    
    disjointSets() {
        const ds = {};
        for(let i = 0; i < this.roots.length; i++) {
          let currentRoot = this.find(i);
          if (currentRoot in ds) {
              ds[currentRoot].push(i);
          } else {
              ds[currentRoot] = [i];
          }
        }
        return ds;
    }
}
Smallest String With Swaps