NC18386—字符串（双指针/尺取法）

链接：https://ac.nowcoder.com/acm/problem/18386链接：https://ac.nowcoder.com/acm/problem/18386

题目描述

小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中，长度最短是多少。

输入描述:

一行一个字符串S。只包含小写字母。S的长度不超过106.

输出描述:

一行一个数字，代表最短长度。数据保证存在一个合法的S的子串。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+50;
string s;
int ans=N,cnt[26];         //用cnt数组储存查询情况，有一个为0都表示不包含所有小写字母

bool judge()               //此函数循环遍历cnt，判断是否有所有小写字母
{
    for(int i=0;i<26;i++)
        if(cnt[i]==0)
            return false;
    return true;    
}
void solve()
{
    cin>>s;                 //输入一个待测字符串
    int l=0,r=0;            //双指针l和r用来移动控制判断
    for(;l<s.size();l++)    //外层左界循环，内层右界循环
    {
        while(r<s.size()&&!judge())
        {
            cnt[s[r]-'a']++;
            r++;
        }
        
        if(judge())
        {
            cnt[s[l]-'a']--;
            ans=min(ans,r-l);
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

l在外层循环，r在内层循环：r循环到满足条件的地方，更新ans，r不动，l往右移动看是否满足，若满足则更新ans，否则r继续移动到下一个满足条件的地方，以此类推只到字符串结尾。