E. 交替字符串 - 详细题解

问题重述

给定一个字符串 $s$，可以通过两种操作将其变为交替字符串（偶数长度，奇数位置字符相同，偶数位置字符相同）：

• 删除操作：删除任意一个字符，最多执行 $1$ 次
• 替换操作：将任意字符替换为其他字母，次数不限

求最少操作次数。

---

关键观察

观察 1：交替字符串的结构

交替字符串长度为偶数，设为 $2k$，则：

• 所有奇数位置（$1,3,5,\dots,2k-1$）的字符相同，设为 $x$
• 所有偶数位置（$2,4,6,\dots,2k$）的字符相同，设为 $y$
• $x$ 和 $y$ 可以相同也可以不同

观察 2：无删除操作的情况

如果原始字符串长度 $n$ 为偶数，我们不需要删除操作（因为删除操作只能使用 $0$ 或 $1$ 次，且会使长度变为奇数，不符合要求）。

此时问题简化为：

• 选择奇数位置的统一字符 $x$
• 选择偶数位置的统一字符 $y$
• 最小化替换次数

计算方法：

• 奇数位置：保留出现次数最多的字符，其余替换
• 偶数位置：保留出现次数最多的字符，其余替换

$$\text{操作次数} = n - (\text{奇数位置最大频数} + \text{偶数位置最大频数}) $$

---

观察 3：需要删除操作的情况

当 $n$ 为奇数时，必须删除一个字符（因为交替字符串长度必须为偶数）。删除后字符串长度变为偶数。

删除位置 $i$ 后：

• 位置 $i$ 之前的字符奇偶性不变
• 位置 $i$ 之后的字符奇偶性翻转（因为所有后面的字符向前移动一位）

---

算法设计

情况 1：$n$ 为偶数

直接统计奇数位和偶数位的字符频数，取最大值：

$$\text{ans} = n - \max_{c}(\text{odd}[c]) - \max_{c}(\text{even}[c]) $$

情况 2：$n$ 为奇数

对于每个可能删除的位置 $i$，计算删除后的最少替换次数，取最小值。

预处理：

• $pref[0][c]$：位置 $i$ 之前（不包括 $i$）的偶数位置中字符 $c$ 的数量
• $pref[1][c]$：位置 $i$ 之前的奇数位置中字符 $c$ 的数量
• $suf[0][c]$：位置 $i$ 之后（不包括 $i$）的偶数位置中字符 $c$ 的数量
• $suf[1][c]$：位置 $i$ 之后的奇数位置中字符 $c$ 的数量

删除位置 $i$ 后的奇偶分布：

• 新的偶数位置 = 删除前偶数位置且 $< i$ + 删除前奇数位置且 $> i$（因为翻转）
• 新的奇数位置 = 删除前奇数位置且 $< i$ + 删除前偶数位置且 $> i$（因为翻转）

因此，新偶数位置中字符 $c$ 的数量为：

$$\text{new\_even}[c] = pref[0][c] + suf[1][c]$$

新奇数位置中字符 $c$ 的数量为：

$$\text{new\_odd}[c] = pref[1][c] + suf[0][c]$$

删除后字符串长度为 $n-1$（偶数），最少替换次数为：

$$\text{cost} = (n-1) - \max_c(\text{new\_even}[c]) - \max_c(\text{new\_odd}[c]) $$

---

算法步骤

1. 读入 $n$ 和字符串 $s$
2. 如果 $n$ 为偶数：
   • 统计奇数位和偶数位的字符频数
   • 输出 $n - \max(\text{odd}) - \max(\text{even})$
3. 如果 $n$ 为奇数：
   • 初始化后缀数组 $suf[2][26]$，统计所有位置的频数
   • 初始化前缀数组 $pref[2][26] = 0$
   • 遍历每个位置 $i$（从左到右）：
     • 从后缀中减去当前位置 $i$ 的贡献
     • 计算删除 $i$ 后的最少替换次数
     • 更新答案
     • 将当前位置 $i$ 的贡献加入前缀
   • 输出最小值

---

完整代码

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

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        
        int res = n;  // 初始化为最大值
        
        if (n % 2 == 0) {
            // 情况1：长度为偶数，不需要删除
            vector<int> odd(26, 0), even(26, 0);
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    even[s[i] - 'a']++;
                } else {
                    odd[s[i] - 'a']++;
                }
            }
            
            int max_odd = *max_element(odd.begin(), odd.end());
            int max_even = *max_element(even.begin(), even.end());
            
            res = n - max_odd - max_even;
        } 
        else {
            // 情况2：长度为奇数，需要删除一个字符
            vector<int> pref[2] = {vector<int>(26, 0), vector<int>(26, 0)};
            vector<int> suf[2] = {vector<int>(26, 0), vector<int>(26, 0)};
            
            // 初始化后缀数组
            for (int i = n - 1; i >= 0; i--) {
                suf[i % 2][s[i] - 'a']++;
            }
            
            // 遍历每个可能删除的位置
            for (int i = 0; i < n; i++) {
                // 从后缀中移除当前位置
                suf[i % 2][s[i] - 'a']--;
                
                // 计算删除当前位置后的最少替换次数
                int ans = n;  // 临时变量
                for (int k = 0; k < 2; k++) {
                    int mx = 0;
                    for (int j = 0; j < 26; j++) {
                        // k=0: 新偶数位置 = 前缀偶数 + 后缀奇数
                        // k=1: 新奇数位置 = 前缀奇数 + 后缀偶数
                        mx = max(mx, suf[1 - k][j] + pref[k][j]);
                    }
                    ans -= mx;
                }
                res = min(res, ans);
                
                // 将当前位置加入前缀
                pref[i % 2][s[i] - 'a']++;
            }
        }
        
        cout << res << endl;
    }
    
    return 0;
}

---

时间复杂度

• 每个测试用例：$O(n \times 26)$
• 总复杂度：$O(\sum n \times 26) \le 2 \times 10^5 \times 26 \approx 5.2 \times 10^6$

---直接相信标程的正确性，并按照标程实现即可。