题目描述

难度分:$1200$

输入$T(\leq 2 \times 10^4)$表示$T$组数据。所有数据的字符串长度之和$\leq 2 \times 10^5$。

每组数据输入一个长度$\leq 2 \times 10^5$的字符串$s$，只包含数字$1$、$2$、$3$。

输出$s$中的最短子串的长度，该子串必须包含所有$1$、$2$、$3$三种字符。

如果没有这样的子串，输出$0$。

输入样例

7
123
12222133333332
112233
332211
12121212
333333
31121

输出样例

3
3
4
4
0
0
4

算法

二分答案

比较容易发现单调性，如果一个长度为$len$的子串包含$1$，$2$，$3$三种数字，那么更长的子串肯定也可以包含这三种数字，因此可以进行二分答案。对于一个给定的子串长度$len$，对$s$串进行滑动窗口，用一个长度为$3$的$counter$数组来维护子数组中$1$、$2$、$3$三种数的频数，有以下两种情况：

1. 如果存在长度为$len$的子串满足条件，记录答案，并往左搜索看能不能使长度更短。
2. 否则说明当前长度给得太苛刻了，往右搜索更大的长度。

复杂度分析

时间复杂度

二分答案的下界是$3$，上界是$n$，每次$check$就是一个$O(n)$的滑动窗口，因此算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的字符串$s$，仅使用了有限几个变量，因此算法的额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n;
char s[N];

bool check(int len) {
    int counter[3] = {0};
    for(int i = 1; i <= len; i++) {
        counter[s[i] - '1']++;
    }
    if(counter[0] && counter[1] && counter[2]) return true;
    for(int i = len + 1; i <= n; i++) {
        int j = i - len;
        counter[s[i] - '1']++;
        counter[s[j] - '1']--;
        if(counter[0] && counter[1] && counter[2]) return true;
    }
    return false;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        int left = 3, right = n, ans = 0;
        while(left <= right) {
            int mid = left + right >> 1;
            if(check(mid)) {
                ans = mid;
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}