C++字符串问题求助：求AB串转为前A后B格式的最少修改次数

看起来你当前的代码逻辑存在一个关键问题：你固定了x为原字符串中A的总数，但实际上最优的分割点x可以是0到n之间的任意值，我们需要遍历所有可能的x，找到能让修改次数最少的那个。

你的代码问题分析 #

比如示例AABAA（n=5），原字符串是A A B A A，其中A的总数是4。你的代码会计算x=4的情况：前4个字符要全A（原前4个是AABA，有1个B需要改成A），后1个字符要全B（原是A，需要改成B），总修改次数是2。但实际上最优的x是5（全A），只需要把字符串中唯一的B改成A，修改次数仅1次——这就是你代码遗漏的情况：没有遍历所有可能的x取值。

正确解法思路 #

我们需要枚举所有可能的分割点x（x的取值范围是0到n，包含0和n）：

• 当x=0时，整个字符串要全为B，修改次数等于原字符串中A的数量；
• 当x=n时，整个字符串要全为A，修改次数等于原字符串中B的数量；
• 当0<x<n时，前x个字符需要全为A（修改次数是前x个字符中B的数量），后n-x个字符需要全为B（修改次数是后n-x个字符中A的数量），总修改次数是这两个数值之和。

为了高效计算每个x对应的修改次数，我们可以预处理一个前缀B数组：

• prefix_b[i]表示前i个字符（索引0到i-1）中B的数量，也就是前i个字符改成全A需要的修改次数。
  同时，我们可以计算整个字符串中A的总数total_a，那么后n-x个字符中的A数量等于total_a - (x - prefix_b[x])（前x个字符中的A数量是x - prefix_b[x]），这部分就是后n-x个字符改成全B需要的修改次数。

正确代码实现 #

#include <iostream>
#include <string>
#include <climits>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        
        // 前缀B数组：prefix_b[i]代表前i个字符中B的数量
        int prefix_b[n + 1];
        prefix_b[0] = 0;
        for (int i = 0; i < n; ++i) {
            prefix_b[i + 1] = prefix_b[i] + (s[i] == 'B' ? 1 : 0);
        }
        
        int total_a = n - prefix_b[n]; // 字符串中A的总数
        int min_mod = INT_MAX;
        
        // 遍历所有可能的分割点x
        for (int x = 0; x <= n; ++x) {
            // 前x个改全A的次数 + 后n-x个改全B的次数
            int mod_count = prefix_b[x] + (total_a - (x - prefix_b[x]));
            if (mod_count < min_mod) {
                min_mod = mod_count;
            }
        }
        
        cout << min_mod << endl;
    }
    return 0;
}

验证示例 #

1. 示例AAB（n=3）：
   前缀B数组为[0,0,0,1]，total_a=2。遍历所有x后，最小修改次数为0（x=2时，前2个是AA，后1个是B，无需修改），符合预期。
2. 示例BABA（n=4）：
   前缀B数组为[0,1,1,2,2]，total_a=2。遍历后最小修改次数为2（x=0全B或x=4全A，都需要修改2次），符合预期。
3. 示例AABAA（n=5）：
   前缀B数组为[0,0,0,1,1,1]，total_a=4。遍历后最小修改次数为1（x=5全A，仅需修改1个B），符合预期。

总结 #

你的原代码错误地将x固定为原字符串中A的数量，遗漏了其他可能的最优分割点。正确的做法是枚举所有x的取值，通过前缀数组高效计算每个x对应的修改次数，最终取最小值。该解法的时间复杂度为O(n)每组测试用例，效率很高。

内容的提问来源于stack exchange，提问作者user12594916