二分，前缀和

题目描述

给定一个字符串 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(nlog(n))$

自己在做这道题的时候没想到线性的，转而考虑$O(nlog(n))$时间复杂度的算法，注意题目数据范围说的是所有T

个样例的数据s的总长度不超过 2×105。

那该怎么思考呢?

注意到题目要求的答案是具有单调性的，也就是说假若某一个长度len满足s中存在一个长度为len的子串使得

存在1，2，3，那么我们最后要求的答案一定在len（包含len）的左边，反之在len（不含len）右边。

用mp_1[i]表示[1…i]的 1 的个数,2和3同理，那么区间[i…j]上 1 的的个数为mp_1[ j ] - mp_1[ i - 1 ];

二分里面的check（len）实现含义如下：
对于len，检查是否有mp_1[i] - mp_1[i - len] > 0（2、3同理）同时存在的情况。（len <= i <= n）

remark:因为可能存在整个s都没有1，2，3同时存在的子串，故需要加以特判

时间复杂度

最坏的情况， t = 1;

|s| = 2*10^5;

此时为$O(nlog(n))$

C++ 代码

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

const int N = 2e5+10;
int t, n;
char s[N];
int mp_1[N], mp_2[N], mp_3[N];

bool check(int medi)
{
    for(int i = medi;i <= n; i++)
    {
        if((mp_1[i] - mp_1[i - medi]) > 0&&(mp_2[i] - mp_2[i - medi]) > 0&&(mp_3[i] - mp_3[i - medi]) > 0)return true;
    }

    return false;
}

int main()
{
   cin>>t;
   while(t--)
   {
       cin>>s;
       n = strlen(s);
       for(int i = 0;i < n; i++)
       {
           if(s[i] == '1')mp_1[i + 1] = mp_1[i] + 1, mp_2[i + 1] = mp_2[i], mp_3[i + 1] = mp_3[i];
           else if(s[i] == '2')mp_2[i + 1] = mp_2[i] + 1, mp_1[i + 1] = mp_1[i], mp_3[i + 1] = mp_3[i];
           else mp_3[i + 1] = mp_3[i] + 1, mp_2[i + 1] = mp_2[i], mp_1[i + 1] = mp_1[i];
       }

       int l = 1, r = n;

       if(!check(n))//特判
       {
        cout<<0<<endl;
        continue;
       }
       while(l < r)//二分
       {
           int medi = (l + r)>>1;
           if(check(medi))r = medi;
           else l = medi + 1;
       }

       cout<<r<<endl;
   }

   return 0;
}