你好！我是你的OI教练。这张图片来到了“左右模式变化”这一大类线性预处理技巧的第三个核心模式——Counting（计数模式）。

你圈出的红框中，典型的应用是解决“左右字符/状态分隔”的问题。与找极大值（Min-Max）或找单调区间（Trend-Based）不同，这次我们是在统计特定元素的出现次数（前缀/后缀频次）。

为了让你在NOI体系中熟练应用这个计数技巧，我们将原知识点转换为标准竞赛辅导流程。请拿出草稿纸，我们一起来推导！

1. NOI风格模拟试题

题目名称： 平衡字符串所需的最少删除次数 (Minimum Deletions to Balance String)

题目描述： 给定一个长度为 $N$ 的字符串 $S$，该字符串仅由字符 'a' 和 'b' 组成。 我们定义一个字符串是平衡的，当且仅当字符串中不存在字符 'b' 出现在字符 'a' 的前面。也就是说，字符串的形式必须是若干个（可以是 0 个）'a'，后面紧跟着若干个（可以是 0 个）'b'。 为了使给定的字符串 $S$ 变得平衡，你可以删除任意位置的字符。请你编写一个算法，计算出使 $S$ 平衡所需的最少删除次数。

输入格式： 第一行包含一个整数 $N$ $(1 \le N \le 10^5)$，表示字符串的长度。 第二行包含一个长度为 $N$ 的字符串 $S$，仅由小写字母 'a' 和 'b' 组成。

输出格式： 输出一个整数，表示最少的删除次数。

样例输入：

8
aababbab

样例输出：

2

样例说明： 有多种最优方案能够以删除 2 个字符的代价使字符串平衡：

• 删除下标为 2 和下标为 5 的字符（即两个 'b'），字符串变为 "aaaabb"。
• 删除下标为 2 的 'b' 和下标为 6 的 'a'，字符串变为 "aabbbb"。 最少删除次数均为 2。

2. 预备知识点总结

在解决这道“计数模式”问题前，你需要掌握：

• 前缀和 / 后缀和数组 (Prefix & Suffix Array)： 这里不再是对数值求和，而是对特定状态/字符出现的频次求和。例如“前缀 'b' 的数量”和“后缀 'a' 的数量”。
• 枚举分割点思想 (Splitting Point Enumeration)： 将一个序列“一分为二”，左半边遵循规则 A，右半边遵循规则 B。全局最优解往往诞生于遍历所有可能的分割线。
• 滚动变量优化 (Space Optimization)： 能够在理解了前后缀数组后，将其转换为 $O(1)$ 空间复杂度的在线统计变量。

3. 启发式教学：草稿纸上的推理过程

同学们，请在草稿纸上写下样例字符串：S = a a b a b b a b。

第一步：暴力思考法（如何才能平衡？）

如果最终字符串是平衡的，那么它一定存在一条**“完美分界线”**：分界线的左边全是 'a'，分界线的右边全是 'b'。（分界线也可以在最左边或最右边，代表全是 'b' 或全是 'a'）。 最暴力的想法是：我们枚举这条分界线 $i$（假设 $i$ 左边全是 'a'，右边全是 'b'）。 对于每一个 $i$，我们需要遍历一遍左边，统计出有多少个 'b' 需要被删掉；再遍历一遍右边，统计出有多少个 'a' 需要被删掉。两者相加就是当前分割方案的删除代价。

• 教练提问： 枚举分界线需要 $O(N)$，每次向左向右扫描统计需要 $O(N)$，总时间复杂度是多少？
• 思考回答： $O(N^2)$。当 $N=10^5$ 时，操作次数达到 $10^{10}$，在 NOI 中一定会 TLE (超时)。

第二步：引入 Counting 计数模式（空间换时间）

注意看图片红框： dpLeft: Count of 'X's to the left. (左侧 'X' 的数量，这题里 'X' 指的是非法出现在左侧的 'b') dpRight: Count of 'Y's to the right. (右侧 'Y' 的数量，这题里 'Y' 指的是非法出现在右侧的 'a')

我们在草稿纸上画格子：

1. 原字符串 S: a a b a b b a b
2. 构建 dpLeft 数组:
   • 含义：dpLeft[i] 表示在下标 $i$ 之前（不包含 $i$），有多少个 'b'。也就是如果我们把分界线划在 $i$ 之前，左半边需要删除的 'b' 的数量。
   • 手推：[0, 0, 0, 1, 1, 2, 3, 3, 4] (注意，分界线有 $N+1$ 个位置，从 $0$ 到 $N$)
3. 构建 dpRight 数组:
   • 含义：dpRight[i] 表示从下标 $i$ 开始到末尾，有多少个 'a'。也就是右半边需要删除的 'a' 的数量。
   • 手推：从右往左数 'a' 的个数：[4, 3, 2, 2, 1, 1, 1, 0, 0]

教练引导核心： 现在，假设我们把分界线定在 $i$（左半部分是 $0 \dots i-1$，右半部分是 $i \dots N-1$）。 此时所需的删除总数就是 dpLeft[i] + dpRight[i]。 比如我们在下标 $3$（就是第二个 'a' 和第二个 'a' 的右侧那个 'b' 之间，即 aab | abbab）划分： dpLeft[3] = 1 (左边有个 'b')， dpRight[3] = 2 (右边有 2 个 'a')。总代价 = $1 + 2 = 3$。 我们只需遍历一次 $i$ 从 $0$ 到 $N$，求出这个和的最小值即可！这就把 $O(N^2)$ 降到了 $O(N)$！

第三步：极简空间优化与伪代码流程图

时间复杂度优化建议： $O(N)$ 的时间已经最优，但我们可以优化空间！ 想一想，既然我们是从左到右遍历分界线，我们完全可以用两个普通变量 b_count_left 和 a_count_right 来替代数组！

• 初始状态下，分界线在最左侧（左侧为空，右侧为整个字符串）：b_count_left = 0，a_count_right = 整个字符串中 a 的总数。
• 我们从左向右移动分界线 $i$：如果滑过的是 'a'，那么右侧的 'a' 少了一个，a_count_right 减一；如果滑过的是 'b'，那么左侧的 'b' 多了一个，b_count_left 加一。
• 每移动一步，更新最小代价。

这样，我们的空间复杂度就被完美压缩到了 $O(1)$！

下面是基于 $O(1)$ 优化的伪代码流程图（已规避特殊符号）：

graph TD
    A(开始) --> B(读入字符串长N和字符串S)
    B --> C(遍历一遍S统计所有字母a的总数 赋值给 a_count_right)
    C --> D(初始化 b_count_left 为 0)
    D --> E(初始化 最小代价 min_del 为 a_count_right)
    E --> F(循环 i 从 0 到 N减1)
    F --> G{当前字符 S的第i项 是字母a吗}
    G -- 是 --> H(a_count_right 减去 1)
    G -- 否 --> I(b_count_left 加上 1)
    H --> J(计算当前代价 current_cost 为 a_count_right 加上 b_count_left)
    I --> J
    J --> K(更新 min_del 为 min_del 和 current_cost 中的较小值)
    K --> L(继续下一个 i 循环)
    L --> M(循环结束)
    M --> N(输出 最小代价 min_del)
    N --> O(结束)

(复杂度和优化分析已经在上述讲解中一并给出：优化后时间复杂度 $O(N)$，空间复杂度 $O(1)$)

4. 读题技巧：此类题型的关键词在哪里？

以后在考场上，当你看到以下关键词组合时，立刻条件反射出**“左右模式：Counting (前后缀计数)”**：

1. “平衡” / “分离” / “左侧都是...右侧都是...”： 例如“让所有的奇数在偶数前面”、“所有的红色珠子在蓝色珠子前面”，这明确指向了寻找一条**“分界线”**。
2. “最少修改次数” / “最少删除操作” / “最少翻转次数”： 题目不要求你实际给出改变后的数组，只求“最少代价”。这种情况下，代价往往等于“不在正确位置上的元素数量统计”。
3. 只有两种状态/两种元素： 例如 'a' 和 'b'、0 和 1、正数和负数。这极大地简化了计数逻辑，只需要统计其中一种或两种的各自前后缀即可。
4. 数据范围 $10^5$： 再次提醒，暴力枚举必然超时，必须通过一次预遍历统计总量（或建立前后缀数组），后续查询必须是 $O(1)$。