LeetCode 1202. Smallest String With Swaps

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        vector<int> f(s.size(), -1);
        vector<vector<int>> m(s.size());
        if (pairs.size() == 0) return s;
        for (auto& p : pairs) {
            auto i = find(f, p[0]), j = find(f, p[1]);
            if (i != j) {
                if (-f[i] < -f[j])
                    swap(i ,j);
                f[i] += f[j];
                f[j] = i;
            }
        }
        for (int i = 0; i < s.size(); ++i)
            m[find(f, i)].push_back(i);
        for (auto& ids : m) {
            string ss = "";
            for (int id : ids)
                ss += s[id];
            sort(ss.begin(), ss.end());
            for (int i = 0; i < ids.size(); ++i)
                s[ids[i]] = ss[i];
        }
        return s;
    }
    int find(vector<int>& f, int i) {
        return f[i] < 0 ? i : f[i] = find(f, f[i]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        class UF:
            def __init__(self, n): self.p = list(range(n))
            def union(self, x, y): self.p[self.find(x)] = self.find(y)
            def find(self, x):
                if x != self.p[x]: self.p[x] = self.find(self.p[x])
                return self.p[x]
        uf, m, ans = UF(len(s)), defaultdict(list), []
        for a, b in pairs: 
            uf.union(a, b)
        for i in range(len(s)): 
            m[uf.find(i)].append(s[i])
        for id in m.keys(): 
            m[id].sort(reverse=True)
        for i in range(len(s)): 
            ans.append(m[uf.find(i)].pop())
        return ''.join(ans)