zd的小窝
0%

CF1354B题解

发表于

看着题解区内没有双指针的做法，这里向大家介绍一下本题双指针的做法。

题目分析

显然，若 $S$ 的一个字串 $T$ 满足题意，则所有包含 $T$ 的字符串均满足题意。

我们不妨从 $1$ 开始，维护两个指针 $l,r$，每次操作使 $r$ 向右尝试增加，判断新的字串是否满足题意，若是，则尝试将 $l$ 右移，尽量缩小字串。

因为首先是满足题意，其次再缩小长度，所以本题的正确性可以得到保证。

时间复杂度分析：因为每个点最多分别被 $l,r$ 扫到一次，所以时间复杂度为 $\Theta(n)$ 可以通过该题。

$code$

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
/*
	Author:zd
	Status:WA on pretest 2
*/

//去掉了快读，快写等函数。 
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define INF 0x7f7f7f7f
void solve();
signed main(){int _;read(_);while(_--)solve();return 0;}
char s[N];
void solve(){
	scanf("%s",s+1);
	int a=0,b=0,c=0,l=0,r=0,n=strlen(s+1);//a,b,c分别维护区间内1,2,3的个数 
	int ans=INF;
	while(r<=n){
		if(a&&b&&c){
			if(s[l]=='1')a--;
			if(s[l]=='2')b--;
			if(s[l]=='3')c--;
			l++;
		}
		else{
			r++;
			if(s[r]=='1')a++;
			if(s[r]=='2')b++;
			if(s[r]=='3')c++;
			
		}
		if(a&&b&&c)cmin(ans,r-l+1);
	}
	if(ans==INF){//判断整个串是否满足题意 
		puts("0");
		return;
	}
	writeh(ans);
}