自定义字符串排序如何按给定字母顺序重排？（LeetCode 791）

简化版

给定 order 表示部分字符的优先顺序，要求重排 s。如果字符集较小，可以先统计 s 中每个字符次数，再按 order 顺序输出出现过的字符，最后输出不在 order 中的剩余字符。

详细版

String customSortString(String order, String s) {
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) cnt[c - 'a']++;
    StringBuilder ans = new StringBuilder();
    for (char c : order.toCharArray()) {
        while (cnt[c - 'a']-- > 0) ans.append(c);
    }
    for (int i = 0; i < 26; i++) {
        while (cnt[i]-- > 0) ans.append((char) ('a' + i));
    }
    return ans.toString();
}

如果字符集不是小写字母，用 Map<Character, Integer> 计数，或者给每个字符建立 rank 后排序。计数法时间 O(n + 字符集大小)。

完整版教学

一、题目不是普通排序

普通字典序会按 'a'..'z' 排，但题目给了一个自定义顺序。例如：

order = "cba"
s = "abcd"

c 要在 b 前，b 要在 a 前；d 不在 order 中，放哪里通常都可以，只要不破坏已指定顺序。

面试抓手：这题的排序规则由 order 给出，未出现的字符只需要保留在结果中，通常没有相对顺序要求。

二、为什么计数排序适合

题目只关心字符出现次数和输出顺序，不关心原来每个字符的位置。小写英文字母只有 26 个，计数数组非常自然。

步骤	做什么
统计	记录 `s` 中每个字符出现几次
输出 order	按自定义顺序消耗计数
输出剩余	把未指定字符补到答案里

这比比较排序更简单，也避免写复杂 comparator。

三、按 order 消耗计数

对 order 中每个字符 c，把 s 里所有 c 都输出。

for (char c : order.toCharArray()) {
    while (cnt[c - 'a'] > 0) {
        ans.append(c);
        cnt[c - 'a']--;
    }
}

写成 cnt-- > 0 也可以，但面试时分开写更不容易看错。

四、剩余字符如何处理

不在 order 中的字符没有相对约束，放在最后即可。它们之间按任意顺序通常都通过；为了稳定和可读，可以按 'a'..'z' 输出。

order = cba
s = abcd
按 order 输出 cba
剩余 d
答案 cbad

如果业务要求保留剩余字符原相对顺序，那就不能简单扫 26 个桶，要在第二遍遍历原串输出未指定字符。

五、字符集变化时怎么改

如果输入不只小写字母，int[26] 会越界或统计错误。可以换成哈希表：

Map<Character, Integer> cnt = new HashMap<>();
for (char c : s.toCharArray()) cnt.merge(c, 1, Integer::sum);

如果需要排序整个字符数组，也可以为 order 建立 rank，不在 order 的字符给默认大 rank。

六、复杂度对比

计数法扫描 s 一次，扫描 order 一次，再扫描字符集一次。小写字母下近似 O(n)。

比较排序写法通常是 O(n log n)，适合字符集复杂但实现限制较少的场景。原题下计数法更贴合。

七、常见误区与追问

误区：直接对 s 做字典序排序。 题目顺序由 order 决定，不是自然字母序。
误区：漏掉不在 order 中的字符。 它们仍然要出现在答案里。
误区：默认字符集一定是 26 个小写字母。 要先看题目约束，泛化场景用 Map。
追问：不在 order 中的字符放哪里？ 原题通常任意；可以统一放最后。
追问：如果要保留剩余字符原顺序？ 先输出指定字符，再按原串顺序输出未指定字符。
追问：计数法复杂度是多少？ 小写字母下 O(n+26)，空间 O(26)。

八、加强记忆

自定义排序题先问“字符集小不小”。小写字母就计数：先数 s，再按 order 倒桶，最后补剩余。不要把它想成复杂排序，核心是“题目给了出桶顺序”。

简化版

详细版