题目描述

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

(滑动窗口) $O(n)$

有点像《操作系统OS》进程中的读写者问题

时间复杂度

参考文献

python3 代码

from collections import defaultdict

T =  int(input())
for _ in range(T):

    nums = input()
    n = len(nums)

    dic = defaultdict(int)
    cnt = 0
    res = float('inf')
    L = 0
    for R in range(n):
        x = int(nums[R])        #进R
        dic[x] += 1
        if dic[x] == 1:
            cnt += 1
        while cnt == 3:         #弹L
            y = int(nums[L])
            res = min(res, R - L + 1)
            dic[y] -= 1
            L += 1
            if dic[y] == 0:
                cnt -= 1
    if res == float('inf'):
        res = 0
    print(res)

C++ 代码

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

int main()
{
    int T;  cin >> T;
    while(T --)
    {
        string s;  cin >> s;
        int n = s.size();
        unordered_map<int, int> dic;

        int res = INT_MAX;
        int cnt = 0;
        int L = 0;
        for (int R = 0; R < n; R ++)
        {
            if (dic[s[R] - '0'] ++ == 0)        //进R
                cnt ++;
            while (cnt == 3)                    //弹L
            {
                res = min(res, R - L + 1);
                if (dic[s[L++] - '0'] -- == 1)
                    cnt --;
            }
        }
        if (res == INT_MAX)
            res = 0;
        cout << res << endl;

    }

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla