题目描述

给你一个字符串s，并且它只包含1，2或3。你需要找一个最短的子串，使得它包含1和2和3。

输入格式

输入包含T组数据。
对于每组数据，输入只有1行，包含一个字符串s。

输出格式

输出共T行，每行包含一个整数，表示答案。如果无解，请输出0。

数据范围

$T<=20000$
s的长度小于等于200000，约定输入的所有s的长度之和不多于200000。

样例

Input:
7
123
12222133333332
112233
332211
12121212
333333
31121

Output:
3
3
4
4
0
0
4

算法

(二分+前缀和) $O(nlogn)$

这个题显然可以暴力，但是绝对超时。代码就不贴了。
我们不难发现本题的答案是具有单调性的，即如果$l$为解，则$l+1$也是一个解。
所以考虑二分，最优性问题转化成快速判断在长度为$len$的所有子串中，存不存在合法解。
O(1)查询的要求让我们自然的想到前缀和，在读入的时候统计一下前缀中1、2、3的个数，就可以在O(1)的时间内完成查询了。
另外，判断一下是否少某种字符就可以快速的判断无解了。

C++ 代码

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

int n;
char str[maxn];
int cnt1[maxn], cnt2[maxn], cnt3[maxn];

bool check(int mid)
{
    for (int i = mid; i <= n; i ++ )
    {
        int c1 = cnt1[i] - cnt1[i - mid];
        int c2 = cnt2[i] - cnt2[i - mid];
        int c3 = cnt3[i] - cnt3[i - mid];
        if (c1 && c2 && c3) return 1;
    }

    return 0;
}

void solve()
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    for (int i = 1; i <= n; i ++ )
    {
        cnt1[i] = cnt1[i - 1] + (str[i] == '1');
        cnt2[i] = cnt2[i - 1] + (str[i] == '2');
        cnt3[i] = cnt3[i - 1] + (str[i] == '3');
    }

    if (!cnt1[n] || !cnt2[n] || !cnt3[n]) puts("0");
    else
    {
        int l = 1, r = n;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }

        cout << r << endl;
    }

    return;
}

int main()
{
    int T;
    cin >> T;
    while (T -- ) solve();

    return 0;
}