# 1202. 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。

参考了[这](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/smallest-string-with-swaps/discuss/388257/C%252B%252B-with-picture-union-find)。

```cpp
/*
 * @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


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/union-find/1202.-smallest-string-with-swaps.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.