5. 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.

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"

Solution: (Using union find)

class Solution
{
public:
    int findPar(vector<int> &v, int node)
    {
        if (v[node] == -1)
        {
            return node;
        }

        v[node] = findPar(v, v[node]);
        return v[node];
    }

    void uni(vector<int> &v, vector<int> &rank, int a, int b)
    {

        int parA = findPar(v, a);
        int parB = findPar(v, b);

        if (parA != parB)
        {

            if (rank[parA] > rank[parB])
            {
                v[parB] = parA;
            }
            else if (rank[parB] > rank[parA])
            {
                v[parA] = parB;
            }
            else
            {
                v[parA] = parB;
                rank[parB]++;
            }
        }

        return;
    }

    string smallestStringWithSwaps(string s, vector<vector<int>> &pairs)
    {

        int n = s.length();

        vector<int> parent(n, -1);
        vector<int> rank(n, 0);

        for (int i = 0; i < pairs.size(); i++)
        {
            uni(parent, rank, pairs[i][0], pairs[i][1]);
        }

        unordered_map<int, vector<int>> m;

        for (int i = 0; i < n; i++)
        {
            m[findPar(parent, i)].push_back(i);
        }

        for (auto itr = m.begin(); itr != m.end(); itr++)
        {
            vector<int> v = itr->second;
            string temp = "";
            for (int i = 0; i < v.size(); i++)
            {
                temp += s[v[i]];
            }

            sort(temp.begin(), temp.end());
            int k = 0;
            
            for (int i = 0; i < v.size(); i++)
            {
                s[v[i]] = temp[k];
                k++;
            }

        }
        
        return s;
    }
};