题目描述

给定一个字符串 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

1.指针之间具有单调性2.明确两个指针的含义

算法1

(双指针算法) $O(n)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int s[4];

int main()
{
    int T;
    cin >> T;

    while(T --)
    {
        char a[N];
        cin >> a;

        int n = strlen(a);

        memset(s,0,sizeof s);

        int res = n + 1;

        for(int i = 0, j = 0; i < n; i ++)//i表示右端点的位置，j表示左边距离i最近且没有冗余元素的点
        {
            s[a[i] - '0'] ++;

            while(s[a[j] - '0'] > 1) 
            {
                s[a[j] - '0'] --;
                j ++ ;
            }
            if(s[1] && s[2] && s[3]) res = min(res,i - j + 1);
        }

        if(res == n + 1) res = 0;

        printf("%d\n", res);


    }
    return 0;
}