LeetCode 1202. 交换字符串中的元素

2023-04-23 HGNULB 约 8 分钟

文章信息 6 个分类 7 个标签

分类

LeetCode CodeTop 中等未解决 1-2 快手

题目描述

✅ 1202. 交换字符串中的元素

题意分析

给定一个字符串和若干下标对，可以任意多次交换某个下标对对应的两个字符，求所有可达到结果中字典序最小的字符串。交换次数没有限制，允许不执行交换，也不要求把每一对只用一次。

字典序先比较最左侧不同的位置，因此越靠前的字符越重要。字符只能沿允许的交换关系移动，不能直接把整个字符串排序；没有参与任何交换关系的位置必须保持原字符。

解法：并查集分组 + 组内排序

核心思路

[!blue]

把每个下标看作图中的节点，每个允许交换对看作一条无向边。沿连接路径反复交换，可以把路径两端的字符互换：先把一端的字符逐步送到另一端，再沿路径反向恢复中间位置。因此同一个连通分量里的任意两个位置都可以互换，也就能够实现任意重排；不同分量之间则没有交换通道。

用并查集合并所有交换对，再按最终根节点给下标分组。find(i) 找到的是整个分量的代表，不能直接用 parent[i]，因为直接父节点未必已经是根。代码通过路径减半和按大小合并，让分组查找保持较低开销。

各分量的字符总数及每个字符的出现次数都固定，只能在本组的位置之间重新分配。按下标从小到大收集一组位置，把对应字符升序排序，再依次填回这些位置即可。

这种安排为什么最优？如果本组某个较小下标放着较大字符，而后面的同组位置还有更小字符，把它们交换就会使整个字符串在最早变化的位置变小。因此最优结果中，本组字符必然按下标升序对应到字符升序。各组互不影响可用字符，这样独立处理所有分量就得到全局字典序最小结果。

分量中的下标可能并不连续，哈希表遍历组的先后也没有意义，所以必须把排序后的字符写回原下标，而不能把一组组字符直接拼接起来。

解题步骤

为每个下标建立并查集节点，合并全部允许交换对。

按下标从小到大遍历，用 find(i) 将它加入对应分量，组内位置因此天然有序。

对每组取出全部字符并升序排序，保留相同字符的全部副本。

将小字符依次填到本组较小下标，返回填好的字符串。

代码实现

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);

        // 交换可无限次使用，等价于把下标按可达性并成连通分量。
        for (List<Integer> p : pairs) {
            uf.union(p.get(0), p.get(1));
        }

        Map<Integer, List<Integer>> groups = new HashMap<>();

        for (int i = 0; i < n; i++) {
            // 必须用 find(i) 取根，parent[i] 只是直接父亲。
            int root = uf.find(i);

            // 下标按递增顺序加入，每组的位置列表天然有序。
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
        }

        char[] res = s.toCharArray();

        for (List<Integer> idxs : groups.values()) {
            char[] chars = new char[idxs.size()];

            for (int i = 0; i < idxs.size(); i++) {
                chars[i] = s.charAt(idxs.get(i));
            }

            // 小字符配小下标，即为该分量能达到的字典序最小。
            Arrays.sort(chars);

            for (int i = 0; i < idxs.size(); i++) {
                res[idxs.get(i)] = chars[i];
            }
        }

        return new String(res);
    }

    static class UnionFind {
        int[] parent;
        int[] size;

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];

            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            while (x != parent[x]) {
                // 路径减半，就地压扁查找路径。
                parent[x] = parent[parent[x]];
                x = parent[x];
            }

            return x;
        }

        void union(int a, int b) {
            int ra = find(a);
            int rb = find(b);

            if (ra == rb) {
                return;
            }

            // 按大小合并，小树挂到大树下。
            if (size[ra] < size[rb]) {
                int t = ra;

                ra = rb;
                rb = t;
            }

            parent[rb] = ra;
            size[ra] += size[rb];
        }
    }
}

import "sort"

type UnionFind struct {
    parent []int
    size   []int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent: parent, size: size}
}

func (uf *UnionFind) find(x int) int {
    for x != uf.parent[x] {
        // 路径减半，就地压扁查找路径。
        uf.parent[x] = uf.parent[uf.parent[x]]
        x = uf.parent[x]
    }
    return x
}

func (uf *UnionFind) union(a, b int) {
    ra := uf.find(a)
    rb := uf.find(b)
    if ra == rb {
        return
    }
    // 按大小合并，小树挂到大树下。
    if uf.size[ra] < uf.size[rb] {
        ra, rb = rb, ra
    }
    uf.parent[rb] = ra
    uf.size[ra] += uf.size[rb]
}

func smallestStringWithSwaps(s string, pairs [][]int) string {
    n := len(s)
    uf := newUnionFind(n)
    // 交换可无限次使用，等价于把下标按可达性并成连通分量。
    for _, p := range pairs {
        uf.union(p[0], p[1])
    }

    groups := make(map[int][]int)
    for i := 0; i < n; i++ {
        // 必须用 find(i) 取根，parent[i] 只是直接父亲。
        root := uf.find(i)
        // 下标按递增顺序加入，每组的位置列表天然有序。
        groups[root] = append(groups[root], i)
    }

    res := []byte(s)
    for _, idxs := range groups {
        chars := make([]byte, len(idxs))
        for i, idx := range idxs {
            chars[i] = res[idx]
        }
        // 小字符配小下标，即为该分量能达到的字典序最小。
        sort.Slice(chars, func(i, j int) bool {
            return chars[i] < chars[j]
        })
        for i, idx := range idxs {
            res[idx] = chars[i]
        }
    }

    return string(res)
}

复杂度分析

时间复杂度：$O((n+m)\alpha(n)+n\log(n+1))$，其中 n 为字符数，m 为交换对数。路径压缩配合按大小合并的均摊查并成本为反阿克曼量级；各组排序总开销不超过对全部字符排序。

空间复杂度：$O(n)$，保存并查集、分组下标、字符缓冲和结果，不需要枚举交换过程。

关键点总结

[!green]

可重复交换产生传递性，连通分量而非单个交换对决定可重排范围。

同组任意重排允许把小字符放到小下标，最早不同位置的比较保证字典序最优。

分量之间不能交换字符，组内也必须保留原来的字符重数。

易错点总结

[!yellow]

直接排序全串，可能把不同分量的字符互换，得到实际上不可达到的结果。

只按给定交换对执行一轮，忽略了重复交换和路径传递带来的其他可达排列。

用直接父节点分组，会把同一分量拆成多组，应通过 find 取最终根。

按哈希组顺序拼接字符，会丢掉各分量在原字符串中的位置分布，必须按原下标填回。

把同组字符去重，会改变字符串长度和字符数量，排序应保留每次出现。

相似题目

题目	难度	关联与区别
1061. 按字典序排列最小的等效字符串	中等	等价分量思路相同，但本题只能重排已有字符，必须保留每个分量中的字符重数。
765. 情侣牵手	困难	同样按交换关系划分连通结构，本题在每个分量内排序得到字典序最小串。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/20792212

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！