问题简述

给定长度为 $n$ 的字符串，包含字符 B、S、C，分别代表白、灰、黑三种颜色。
寻找最长的连续子串，满足：

• 子串中三种颜色的出现次数互不相同
• 允许某种颜色缺失（出现次数为 0）

关键观察

1. 条件转换：设子串中 B、S、C 的数量分别为 $b, s, c$，要求 $b, s, c$ 互不相等
2. 特殊情况：如果子串只有 1 或 2 种颜色，只要数量不同就满足条件
3. 三种颜色都存在时：必须满足 $b \neq s \neq c \neq b$

核心思路

方法：前缀和 + 条件检查

1. 前缀和预处理：

   preB[i] = 前i个字符中'B'的数量
   preS[i] = 前i个字符中'S'的数量  
   preC[i] = 前i个字符中'C'的数量
   

2. 检查区间 [l, r]：

   b = preB[r] - preB[l-1]
   s = preS[r] - preS[l-1]
   c = preC[r] - preC[l-1]
   

   检查是否 $b, s, c$ 互不相等

优化策略

直接枚举所有区间会超时（$O(n^2)$），需要优化：

1. 固定右端点，寻找最远左端点：

   • 对于每个右端点 $r$，找到最小的 $l$ 使得 $[l, r]$ 满足条件
   • 用双指针或记录最近合法位置

2. 关键性质：
   对于任意右端点 $r$，只需要检查少数几个候选左端点：

   • 最近的出现某种颜色数量相等的位置
   • 具体来说，维护每种 $(b-s, s-c)$ 差值最近出现的位置

算法步骤

1. 读入 $n$ 和字符串 $s$
2. 计算三种颜色的前缀和数组
3. 初始化答案 $ans = 0$
4. 使用哈希表记录 $(b-s, s-c)$ 最近出现的位置
5. 遍历右端点 $r = 1$ 到 $n$：
   • 计算当前 $b, s, c$
   • 检查所有可能破坏条件的差值组合，找到最近的合法左端点
   • 更新答案 $ans = \max(ans, r - l + 1)$
   • 更新哈希表
6. 如果 $ans \geq 1$ 输出 $ans$，否则输出 "NIE"

复杂度分析

• 时间复杂度：$O(n)$，每个右端点只检查常数个候选位置
• 空间复杂度：$O(n)$，存储前缀和和哈希表

样例验证

样例1：CBBSSBCSC

• 最长合法子串：BSSBCS（位置 2-7）
• $b=2, s=3, c=1$，互不相等 ✓
• 长度 = 6

样例2：BBBBC

• 整个字符串：$b=4, c=1$（缺少灰色）
• 4 ≠ 1 ≠ 0，满足条件 ✓
• 长度 = 5

实现要点

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<int> preB(n+1), preS(n+1), preC(n+1);
    for (int i = 0; i < n; i++) {
        preB[i+1] = preB[i] + (s[i] == 'B');
        preS[i+1] = preS[i] + (s[i] == 'S'); 
        preC[i+1] = preC[i] + (s[i] == 'C');
    }
    
    map<pair<int, int>, int> last_pos;
    last_pos[{0, 0}] = 0;
    int ans = 0;
    
    for (int r = 1; r <= n; r++) {
        int b = preB[r], s = preS[r], c = preC[r];
        
        // 检查所有可能使条件不成立的差值组合
        vector<pair<int, int>> candidates = {
            {b - s, s - c}, {b - s, b - c}, {s - b, s - c},
            {s - b, c - s}, {c - b, b - s}, {c - b, c - s}
        };
        
        int min_l = r;
        for (auto key : candidates) {
            if (last_pos.count(key)) {
                min_l = min(min_l, last_pos[key] + 1);
            }
        }
        
        if (min_l <= r) {
            int len = r - min_l + 1;
            int b_cnt = preB[r] - preB[min_l-1];
            int s_cnt = preS[r] - preS[min_l-1];
            int c_cnt = preC[r] - preC[min_l-1];
            
            if (b_cnt != s_cnt && s_cnt != c_cnt && c_cnt != b_cnt) {
                ans = max(ans, len);
            }
        }
        
        last_pos[{b - s, s - c}] = r;
    }
    
    if (ans == 0) cout << "NIE" << endl;
    else cout << ans << endl;
    
    return 0;
}

这种方法利用差值哈希和最近位置记录，在 $O(n)$ 时间内找到最优解。