1202. Smallest String With Swaps

https://leetcode.com/problems/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"

Constraints:

• 1 <= s.length <= 10^5

• 0 <= pairs.length <= 10^5

• 0 <= pairs[i][0], pairs[i][1] < s.length

• s only contains lower case English letters.

给一个字符串s和一系列pair，能根据pair指定的index无限次swap s中对应的字符，问能得到字典序最小的字符串是什么。当多个pairs元素有交集时，它们中任何元素都能通过内部swap到任意位置，每步swap相当于往预定方向前进一步，依次从小到大让每个元素走到对应的位置。因此找出所有有交集的pair集合，并对子集做排序后放回s。合并集合用UF。

参考了这。

/*
 * @lc app=leetcode id=1202 lang=cpp
 *
 * [1202] Smallest String With Swaps
 */

// @lc code=start
class Solution {
public:
    class UF {
    public:
        vector<int> parents;
        void un(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                parents[x] = y;
            }
        }
        int find(int x) {
            while (x != parents[x]) {
                x = parents[x];
                parents[x] = parents[parents[x]];
            }
            return x;
        }
        UF(int N): parents(N) {
            for (int i = 0; i < N; ++i) {
                parents[i] = i;
            }
        }
    };
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        const int N = s.size();
        UF uf(N);
        for (const auto &p : pairs) uf.un(p[0], p[1]);
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < N; ++i) m[uf.find(i)].push_back(i);
        for (const auto &p : m) {
            stringstream ss;
            for (const auto i : p.second) ss << s[i];
            auto ss_s = ss.str();
            sort(ss_s.begin(), ss_s.end());
            for (int i = 0; i < ss_s.size(); ++i) s[p.second[i]] = ss_s[i];
        }
        return s;
    }
};
// @lc code=end