一、题目回顾（精简版）

给定一个仅由 $1,2,3$ 组成的字符串 $s$，要求找到最短的连续子串，满足： 子串中同时包含 $1、2、3$ 各至少一个。 若不存在这样的子串，输出 $0$。

二、标程核心思路（最关键的观察）

核心规律

因为字符串只有 $1、2、3$ 三种字符，满足条件的最短子串一定满足这个结构： A + B + A

• 两端是相同字符 $A$
• 中间是不同字符 $B$
• 整体长度 = 中间段长度 $+ 2$

举个例子：

• 2 1 3 → 对应段压缩后 2,1,3 → 满足 A≠C，长度 $3=1+2$
• 3 11 2 → 对应段压缩后 3,11,2 → 满足 A≠C，长度 $4=2+2$

解题步骤

1. 连续段压缩：把连续相同的字符合并成 (字符, 长度) 例如：1222213 → 压缩为 [(1,1), (2,4), (1,1), (3,1)]
2. 枚举中间段：遍历压缩后的数组，检查第 $i-1$ 个字符 ≠ 第 $i+1$ 个字符 满足则说明这三段组合包含了全部 $1、2、3$
3. 计算长度：满足条件的子串长度 = 中间段长度 $+ 2$，维护最小值
4. 结果判断：无满足条件的情况输出 $0$

三、标程代码逐行详解

#include<bits/stdc++.h>  // C++万能头文件，包含所有常用库
using namespace std;

char buf[200043];  // 缓存输入字符串（高效读取）

int main()
{
	int t;
	scanf("%d", &t);  // 读取测试用例数量 t
	
	for(int i = 0; i < t; i++)  // 遍历每个测试用例
	{
		scanf("%s", buf);       // 读取字符串
		string s = buf;
		int ans = int(1e9);     // 初始化答案为极大值 1e9
		int n = s.size();      // 字符串长度
		
		// 第一步：连续段压缩，存储 (字符, 连续出现次数)
		vector<pair<char, int> > c;
		for(auto x : s)
		{
			// 空数组 或 当前字符和最后一段不同 → 新建段
			if(c.empty() || c.back().first != x)
				c.push_back(make_pair(x, 1));
			// 当前字符和最后一段相同 → 长度+1
			else
				c.back().second++;
		}
		
		// 第二步：枚举中间段，检查条件
		int m = c.size();
		for(int i = 1; i < m - 1; i++)  // i 是中间段索引，必须有左右邻居
		{
			// 核心判断：左边字符 ≠ 右边字符 → 三段包含全部1、2、3
			if(c[i - 1].first != c[i + 1].first)
				// 更新最小长度：中间段长度 + 2
				ans = min(ans, c[i].second + 2);
		}
		
		// 第三步：结果处理，无答案输出0
		if(ans > n) ans = 0;
		printf("%d\n", ans);
	}
}

四、关键逻辑公式化

1. 压缩规则 连续相同字符 $\rightarrow$ $\boldsymbol{(ch, len)}$，$len$ 为连续出现次数。

2. 判断条件 对于压缩数组中索引为 $i$ 的元素： $\boldsymbol{c[i-1].first \neq c[i+1].first}$

3. 长度计算 满足条件的子串长度 = $\boldsymbol{c[i].second + 2}$

4. 答案规则

• 若最终 $ans < 10^9$ → 输出 $ans$
• 否则 → 输出 $0$

五、样例推演（验证正确性）

以样例输入 31121 为例：

1. 原字符串：3 11 2 1
2. 压缩结果：[(3,1), (1,2), (2,1), (1,1)]
3. 遍历中间段：
   • $i=1$：左=3，右=2 → 不相等 ✔️
   • 长度 = $2+2=4$ → 最终答案 $4$

完全匹配样例输出！

六、复杂度分析

• 时间复杂度：$O(n)$ 压缩字符串 $O(n)$ + 遍历压缩数组 $O(n)$，总复杂度线性。
• 空间复杂度：$O(n)$ 存储压缩后的字符段，最坏情况（无连续重复）占用 $O(n)$ 空间。

总结

1. 本题最优解法是连续段压缩 + 枚举检查，对标官方标程；
2. 核心判断：三段式结构中，左右字符不同则包含全部三种字符；
3. 最短长度公式：$\boldsymbol{中间段长度+2}$；
4. 时间复杂度 $O(n)$，适合大数据范围。