B. 替换字符 详细题解

问题描述

给定一个长度为 $n$（$1 \le n \le 10$）的字符串 $s$，仅由小写字母组成。你必须恰好执行一次操作：选择两个下标 $i$ 和 $j$（可以相等），然后将 $s_i$ 赋值为 $s_j$。操作后，我们考虑新字符串的不同排列的数量。目标是使得这个数量最小，并输出任意一个达到最小值的字符串。

关键观察

一个字符串的不同排列数由字符的频率决定：若共有 $k$ 种不同字符，频率分别为 $f_1, f_2, \dots, f_k$，则排列数为

为了最小化该值，我们需要使频率分布尽可能不均匀，因为越不均匀，分母越大，排列数越小。例如，将一种字符的频率增加到 $n$，其余为 $0$，则排列数为 $1$（所有字符相同）。但操作只能执行一次，且只能将一个字符改为另一个字符（可以改自己，即不变）。因此，我们只能将某个出现次数最少的字符改为某个出现次数最多的字符（或改为自身，但那样无变化，通常不会最优）。

贪心策略

• 找到出现次数最少的字符：若有多个，选择字母顺序更小的（因为改变后需要最小化排列数，但优先考虑次数最少，字母顺序只是用来确定一个具体字符）。
• 找到出现次数最多的字符：若有多个，选择字母顺序更大的（同样，次数优先，字母顺序作为次选）。
• 将任意一个出现次数最少的字符（即该字符的一个位置）替换为出现次数最多的字符。

为什么这样贪心是正确的？

• 将出现次数最少的字符改为出现次数最多的字符，可以最大程度地增加一种字符的频数，同时减少另一种字符的频数，使频率分布更极端，从而最小化排列数。
• 选择字母顺序更小的最少字符和字母顺序更大的最多字符只是为了确定唯一性，不影响排列数（因为排列数与字符本身无关，只与频率有关）。

算法步骤

1. 统计每个字母的出现次数 $occ[0..25]$。
2. 遍历字符串，找到出现次数最少的字母（次数最小，次数相同时取字母较小的）和出现次数最多的字母（次数最大，次数相同时取字母较大的）。
3. 在字符串中任选一个出现次数最少字母的位置，将其替换为出现次数最多的字母。
4. 输出修改后的字符串。

时间复杂度

$O(n)$ 每个测试用例，$n \le 10$，$t \le 500$，非常快。

标程代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> occ(26);
        for (char c : s) occ[c - 'a']++;
        
        // 找到出现次数最少和最多的字符（及它们的索引位置）
        pair<pair<int,char>, int> low, high;
        low = high = {{occ[s[0]-'a'], s[0]}, 0};
        for (int i = 1; i < n; i++) {
            low = min(low, {{occ[s[i]-'a'], s[i]}, i});
            high = max(high, {{occ[s[i]-'a'], s[i]}, i});
        }
        // 替换
        s[low.second] = s[high.second];
        cout << s << '\n';
    }
    return 0;
}

样例验证

以第一个样例 "abc" 为例：

• 出现次数：a:1, b:1, c:1。最少次数为 $1$，有多个，取字母最小的 'a'；最多次数为 $1$，有多个，取字母最大的 'c'。将第一个 'a' 替换为 'c'，得到 "cbc"，排列数为 $3$，是最优的。

其他样例同理。

总结：本题的核心是理解排列数与频率的关系，通过一次替换使频率分布尽可能极端，从而最小化排列数。贪心策略简单有效。