题目描述

给定一个字符串 s，其中的每个字符都是 1,2 或 3。

请你求出同时包含字符 1,2,3 的 s 的最短子串的长度。

注意，子串必须是连续的。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含一个字符串 s，保证 s 中可能包含字符 1,2 或 3。

输出格式
每组数据输出一行，一个整数，表示符合条件的最短子串的长度。

如果不存在符合条件的子串，则输出 0。

数据范围
1≤T≤20000,
1≤|s|≤2×105,
所有 T 个输入字符串的长度之和保证不超过 2×105。

样例

输入样例：
7
123
12222133333332
112233
332211
12121212
333333
31121
输出样例：
3
3
4
4
0
0
4

算法

(三指针 枚举) $O(n)$

首先注意到性质,最优解里面,当前子串最左面的元素和最右面的元素一定都只出现了一次,不然就可以替换掉更里面的那个相同元素得到更优解.

故只需要开三个指针分别记录上一次的‘1’,‘2’,‘3’的位置,然后在扫描到当前位置时,更新对应的指针位置,然后求区间长度就行了,我这里是用笨方法,找到三个指针位置中的最大值减去最小值+1后得到区间长度

#include <bits/stdc++.h>
using namespace std;

int n;

int main()
{
    cin>>n;
    while (n -- ){
        string a;
        cin>>a;

        int ans=2e5+10;
        int i1=-1,i2=-1,i3=-1;

        for(int i=0;i<a.size();i++){
            if(a[i]=='1'){
                i1=i;
                if(i1>=0&&i2>=0&&i3>=0){
                    ans=min(ans,max(max(i1,i2),i3)-min(min(i1,i2),i3)+1);
                }
            }
            if(a[i]=='2'){
                i2=i;
                if(i1>=0&&i2>=0&&i3>=0){
                    ans=min(ans,max(max(i1,i2),i3)-min(min(i1,i2),i3)+1);
                }
            }
            if(a[i]=='3'){
                i3=i;
                if(i1>=0&&i2>=0&&i3>=0){
                    ans=min(ans,max(max(i1,i2),i3)-min(min(i1,i2),i3)+1);
                }
            }
        }
        if(ans!=2e5+10) cout<<ans<<endl;
        else cout<<0<<endl;
    }
    return 0;
}