字符串 (尺取法)

尺取法??好奇怪的名字.大概也就是让两个指针相互追逐,核心就是两个指针都是单调的,光往前不后退.从这一点看出复杂度就是 $O(n)$ 的.
这里简单的说明一下这一道题符合为什么符合这个要求,其实这道题的本质也就是对于每一个 $r$ (区间右端点)找一个符合条件最大的 $l$ (区间左端点)
然后对所有的 $r$ 计算一下区间长度,取最小值.
考虑我们已经知道了 $r_i$ 的符合要求的最大 $l_i$ ,考虑 $r_{i+1}$ 的符合要求最大 $l_{i+1}$ ,由于 $l_i-r_i$ 已经符合要求了,所以 $l_{i}-r_{i+1}$ 必定符合要求.(因为我们的 $r$ 是递增,也就是枚举每一位当做 $r$ )
这个时候 $r_{i+1}$ 的最大符合条件的左端点一定 $l_{i+1}$ >= $l_i$ ,所以可以发现左端点是单调不降的.就可以愉快的这样写了.

#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define RE register
#define P 999911659
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define rep(x,y,z) for(RE int x=y;x<=z;++x)
#define fep(x,y,z) for(RE int x=y;x>=z;--x)
#define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=1e6+10;
int cnt[30];
char c[N]; 

char *fs,*ft,buf[1<<15];
//inline char getc() {retur1n (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}

inline bool check()
{
    rep(i,0,25) if(!cnt[i]) return false;
    return true;
}

int main()
{
    //freopen("1.in","r",stdin);
    scanf("%s",c+1);
    int n=strlen(c+1);
    bool flag=false;
    int l=1,ans=INF;
    rep(r,1,n)
    {
        cnt[c[r]-'a']++;
        if(!flag&&check()) flag=true; 
        while(flag&&cnt[c[l]-'a']>1) cnt[c[l]-'a']--,++l;
        if(flag) ans=min(ans,r-l+1);
    }
    put(ans);
    return (0^_^0);
}