非递减字符串

形式化题目

给定一个长度为 $n$ 的、仅由字符 A 和 B 组成的字符串 $S$ 。每次操作可以把任意一个字符翻成另一个（A 变 B 或 B 变 A）。求最少多少次操作后，字符串变成非递减的。

非递减是指不存在一对 $i<j$ 满足 $S_i=B$ 且 $S_j=A$ ，等价于最终串形如 $A^p B^{n-p}$ ：所有 A 都在所有 B 的前面。

思路

一句话本质：先刻画最终答案的形态——非递减的 A/B 串只能是"若干个 A 后面跟若干个 B"，只有 $n+1$ 种；枚举每种形态，用前缀和 $O(1)$ 算出把它变出来的翻转次数，取最小。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 15:54
 * update_at: 2026-09-06 15:57
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举每个位置翻还是不翻。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
char s[MAXN];
int choose[MAXN]; // choose[i] = 0 表示第 i 位不翻，1 表示翻
int ans;

// 判断当前 choose[] 对应的翻转方案是否把字符串变成非递减。
bool check() {
    bool seenB = false;
    for (int i = 1; i <= n; i++) {
        char c = s[i];
        if (choose[i] == 1) c = (c == 'A' ? 'B' : 'A'); // 翻转过后的字符
        if (c == 'B') seenB = true;
        if (seenB && c == 'A') return false; // B 后面出现了 A，不是非递减
    }
    return true;
}

// 统计当前方案的翻转次数。
int calc_answer() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose[i] == 1) cnt++;
    }
    return cnt;
}

void dfs(int dep) {
    if (dep == n + 1) {
        if (check()) {
            ans = min(ans, calc_answer());
        }
        return;
    }

    // 这一层决定第 dep 个位置翻还是不翻。
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> (s + 1);
    n = strlen(s + 1);
    ans = n; // 最多翻 n 次

    dfs(1);

    cout << ans << "\n";
    return 0;
}

这个暴力把问题看成一串 01 选择：choose[i] = 0/1 表示第 i 个字符不翻 / 翻。递归先生成完整的 choose[]，到叶子节点再检查翻转后的串是否非递减，若是就用翻转次数更新答案。它枚举了全部 $2^n$ 种翻转方案，只适合 $n \leqslant 20$ 的小数据。

问题？ 这个暴力慢在哪里？

$2^n$ 种方案， $n = 10^6$ 时完全枚举不完。而且大部分方案是多余的：我们其实不关心"具体翻了哪些位置"，只关心"最后的结果是否非递减"。

问题？ 非递减的最终串长什么样？

非递减 = 不存在 $i<j$ 使 $S_i=B, S_j=A$ 。也就是说 B 一旦出现，后面就不能再有 A。所以最终串里所有的 A 必然集中在前面，所有的 B 集中在后面，形如：

\underbrace{A\ldots A}_{p\ \text{个}}\ \underbrace{B\ldots B}_{n-p\ \text{个}}

设最终串里有 $p$ 个 A（ $0 \leqslant p \leqslant n$ ），则最终串被 $p$ 唯一确定。候选形态从 $2^n$ 个"翻转方案"降为 $n+1$ 个"最终形态"。

问题？ 把 $S$ 变成 $A^p B^{n-p}$ 需要翻几次？

逐位独立地看：前 $p$ 位目标都是 A，其中是 B 的都要翻；后 $n-p$ 位目标都是 B，其中是 A 的都要翻。所以

\text{cost}(p) = (\text{前 } p \text{ 位中 B 的个数}) + (\text{后 } n-p \text{ 位中 A 的个数})

问题？ 怎么快速算这两个计数？

前缀和。设 $preB[i]$ 为前 $i$ 位中 B 的个数， $preA[i]$ 为前 $i$ 位中 A 的个数，则

\text{cost}(p) = preB[p] + \big(preA[n] - preA[p]\big)

下面这张表用样例 #1（AABBA）展示全部 6 种形态的代价：

$p$ （最终 A 的个数）	最终形态	前 $p$ 位中的 B（要翻）	后 $n-p$ 位中的 A（要翻）	代价
0	BBBBB	0	3	3
1	ABBBB	0	2	2
2	AABBB	0	1	1
3	AAABB	1	1	2
4	AAAAB	1	1	2
5	AAAAA	2	0	2

看 $p=2$ 这一行：前 2 位 AA 已经是 A，不用翻；后 3 位 BBA 里只有最后那个 A 要翻成 B，总代价 1。这就是样例的答案。

问题？ 枚举 $p$ 会不会漏掉答案？

不会。任何合法的最终串都必须非递减，而非递减的串必然形如 $A^p B^{n-p}$ ，所以 $p$ 从 $0$ 枚举到 $n$ 覆盖了全部合法形态。每个形态的代价用前缀和精确算出，取最小即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 15:54
 * update_at: 2026-09-06 15:57
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n;
char s[MAXN];
int preA[MAXN]; // preA[i] 表示前 i 位中 A 的个数
int preB[MAXN]; // preB[i] 表示前 i 位中 B 的个数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> (s + 1);
    n = strlen(s + 1);

    // 前缀计数：preA[i]、preB[i]
    for (int i = 1; i <= n; i++) {
        preA[i] = preA[i - 1] + (s[i] == 'A');
        preB[i] = preB[i - 1] + (s[i] == 'B');
    }

    // 枚举最终形态：前 p 位全 A，后 n-p 位全 B
    int ans = n;
    for (int p = 0; p <= n; p++) {
        // 前 p 位里的 B 要翻成 A；后 n-p 位里的 A 要翻成 B
        int cost = preB[p] + (preA[n] - preA[p]);
        ans = min(ans, cost);
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间：前缀统计 $O(n)$ ，枚举 $p$ 共 $n+1$ 次、每次 $O(1)$ ，总 $O(n)$ 。
空间： $O(n)$ （两个前缀计数数组）；也可以只扫两遍做到 $O(1)$ 额外空间。

总结

核心转化一（刻画形态）："非递减"这个全局条件等价于最终串形如 $A^p B^{n-p}$ ，只有 $n+1$ 种候选，把枚举量从 $2^n$ 降到 $n+1$ 。
核心转化二（代价公式）：翻转逐位独立，固定 $p$ 时代价就是"前 $p$ 位里的 B + 后 $n-p$ 位里的 A"，用前缀和 $O(1)$ 求出。
可迁移思想：遇到"最少操作使序列满足某种性质"的题，先想最终序列长什么样、有多少种形态；形态数少就枚举形态，再用前缀和 / DP 快速求每种形态的代价。

目录

形式化题目

思路

代码

复杂度

总结