「POI2011 R2」差值 Difference 题解

题目解析

我们需要在字符串中找到一个子串，使得该子串中出现次数最多的字母与出现次数最少的字母（必须至少出现一次）的出现次数之差最大。

关键约束：

• 最少出现的字母必须至少出现一次
• 如果子串只有一种字母，差值为0
• 字符串长度可达 $10^6$，需要高效算法

算法思路

核心观察

这个问题可以转化为：对于任意两种不同的字母 a 和 b，找到子串使得 a 和 b 的出现次数之差最大。

重要思路：

• 只考虑两种字母的情况，因为最优解必然只涉及两种字母（如果涉及三种，去掉出现次数居中的那种不会使差值变小）
• 将问题转化为最大子段和问题

转化方法

对于每对字母 (a, b)：

• 在字符串中，将 a 标记为 +1，b 标记为 -1，其他字母标记为 0
• 那么 a 和 b 的出现次数之差就是这个序列的子段和
• 我们需要找到最大的子段和

但是有一个重要限制：子串中必须同时包含 a 和 b（即 +1 和 -1 都要出现）

高效解法

我们可以枚举所有26×25=650对字母，但需要 $O(n)$ 处理每对字母。

优化策略： 对于固定的一对字母 (x, y)：

1. 遍历字符串，维护：

   • diff：当前 x 比 y 多出现的次数
   • min_diff：历史上最小的 diff 值
   • last_x：最近一次遇到 x 时的位置
   • last_y：最近一次遇到 y 时的位置

2. 当遇到 x 时：diff++ 当遇到 y 时：diff-- 遇到其他字母时：不变

3. 关键技巧：只有当 last_x 和 last_y 都出现过时，才能用 diff - min_diff 更新答案 因为 diff - min_diff 表示从某个历史位置到当前位置，x 比 y 多出现的最大次数

算法步骤

1. 枚举所有字母对 (x, y)，其中 x ≠ y
2. 对于每对字母：
   • 初始化 diff = 0, min_diff = 0, last_x = -1, last_y = -1, ans = 0
   • 遍历字符串：
     • 更新 diff 和 min_diff
     • 如果当前字符是 x，更新 last_x
     • 如果当前字符是 y，更新 last_y
     • 如果 last_x ≠ -1 且 last_y ≠ -1，用 diff - min_diff 更新答案
3. 输出最大答案

复杂度分析

• 时间复杂度：$O(26^2 × n) = O(676n)$，对于 $n = 10^6$ 是可接受的
• 空间复杂度：$O(n)$ 存储字符串

算法特点

• 枚举简化：将复杂的最优化问题简化为枚举字母对
• 转化技巧：将出现次数差转化为子段和问题
• 高效处理：利用历史最小值技巧在 $O(n)$ 时间内处理每对字母

这种方法充分利用了字母表大小有限的特点，将看似 $O(n^2)$ 的问题转化为 $O(n)$ 的可解问题。