交换字符串中的元素 图解题解

字典序最小，可动的到底是哪些位置

给一个字符串 s 和若干个下标对 pairs，每一对里的两个位置可以无限次互相对调。要问把这些交换用到头，s 能变成的字典序最小串是什么。题面 s="dcab"、pairs=[[0,3],[1,2]]，答案是 "bacd"；若再补一对 [0,2]，四个位置连成一片，答案能小到 "abcd"。要留意：能换的是位置，不是某个字母，相同字母落在不同位置未必能凑到一块。

一对一对手动交换，行不通在哪

pairs 只给出几对下标，真按它一对一对地换、再枚举所有交换顺序，组合数会随对数指数膨胀，根本试不完。何况一对能换无数次，还能借共同下标一环扣一环传下去：0 和 2 能换、2 和 4 能换，0 和 4 没直接配过对，也能通过 2 挪到一起。手动模拟数不清顺序，也抓不住这种间接连通。

先弄清哪些下标属于同一组

把每个下标看成一个点，每对 pairs 看成把两个点连起来。能直接或间接连到一起的下标，构成一个连通分量——里头任意两下标都能顺着对调互相走到，这些位置上的字符可以任意重排。求这种分组用并查集最省事：并查集，即把互相能换到的下标一点点收拢到同一个代表下面，合并时让一个的代表指向另一个，查代表时顺着指向找到根。m 对下标合并完，每个下标归哪组就定死了。

组内排升序，再按下标从小到大填

分组只解决了谁和谁能换，还得摆成字典序最小。对每一组：把组里所有位置上的字符抽出来排成升序，再把组里的下标也从小到大排好，然后让最小字符落最小下标、次小落次小，一一对应。字典序看的是从左往右第一个不同的位置，越靠前的下标越该放小字符，每组内部都让小字符占小位置，整串就压到最小。参考代码换了个等价写法：每组字符降序存着，填回时从尾部弹出最小的，落点完全一样。

"dcab" 配上 [[0,3],[1,2]] 怎么排

按题面走一遍。s="dcab"，下标 0 到 3 上是 d、c、a、b。第一对 [0,3] 把 0、3 并一组，第二对 [1,2] 把 1、2 并一组，得两组：{0,3} 和 {1,2}。看 {0,3}：位置 0 是 d、位置 3 是 b，两个字符排升序是 b、d，下标升序是 0、3，于是 b 进 0、d 进 3。看 {1,2}：位置 1 是 c、位置 2 是 a，排升序是 a、c，下标升序是 1、2，于是 a 进 1、c 进 2。四个位置落定 b、a、c、d，读出来正是 "bacd"。若再加一对 [0,2]，四位连成一整组，d、c、a、b 整体排成 a、b、c、d 填回，收紧到 "abcd"。

复杂度与两处一写就崩的地方

设串长 n、下标对数 m。m 次合并加上按下标查根，路径压缩后近似线性，是 O((n+m)α)，α 增长极慢，当常数看即可；各组字符加起来总共 n 个，排序合计 O(n log n)，两者相加是总时间。空间上 parent 数组和分组存放的字符都随串长走，是 O(n)。有两处一写就崩：并查集若建在字符上而不是下标上，相同字母在不同位置会被硬并成一组，答案立刻散架；字符排好序却忘了按下标升序填回，只排字符不管位置，逐位最小就守不住。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        n = len(s)
        p = list(range(n))
        for a, b in pairs:
            p[find(a)] = find(b)
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[find(i)].append(c)
        for i in d.keys():
            d[i].sort(reverse=True)
        return "".join(d[find(i)].pop() for i in range(n))

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        int p[n];
        iota(p, p + n, 0);
        vector<char> d[n];
        function<int(int)> find = [&](int x) -> int {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        };
        for (auto e : pairs) {
            int a = e[0], b = e[1];
            p[find(a)] = find(b);
        }
        for (int i = 0; i < n; ++i) {
            d[find(i)].push_back(s[i]);
        }
        for (auto& e : d) {
            sort(e.rbegin(), e.rend());
        }
        for (int i = 0; i < n; ++i) {
            auto& e = d[find(i)];
            s[i] = e.back();
            e.pop_back();
        }
        return s;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int[] p;

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        p = new int[n];
        List<Character>[] d = new List[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            d[i] = new ArrayList<>();
        }
        for (List<Integer> pair : pairs) {
            int a = pair.get(0), b = pair.get(1);
            p[find(a)] = find(b);
        }
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; ++i) {
            d[find(i)].add(cs[i]);
        }
        for (List<Character> e : d) {
            e.sort((a, b) -> b - a);
        }
        for (int i = 0; i < n; ++i) {
            List<Character> e = d[find(i)];
            cs[i] = e.remove(e.size() - 1);
        }
        return String.valueOf(cs);
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}