题解 | #字符串#

字符串

思路: 数据范围给的是1e6 如果采用普通的枚举思路的话就要枚举所有区间(i,j) 这样复杂度过高过不了我们就要想办法优化一些，我们可以从暴力的角度来思考看那些是无用功；假设str(i,j) 已经包含了一个合法的子串 此时对于j指针往后移动已经是无用功，题目要求是长度最短。我们这时候应该移动i指针，缩小区间判断是否还满足合法子串，如何判断合法呢，可以用一个数组标记'a'-'z'所有字母遍历是否都不为0，如果都不为0就满足合法定义，如果不满足，就继续移动j指针来确保区间中包含26个小写字母，对于i，j指针都不会回退复杂度为O(2n)。

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string str;
int book[26];
int check()
{
    for(int i=0;i<26;i++)
        if(!book[i])
            return 0;
    return 1;
}
int main()
{
    cin>>str;
    int n=str.size();
    int ans=1e6+10;
    for(int l=0,r=0;r<n;r++)
    {
        book[str[r]-'a']++;
        while(check()) ans=min(ans,r-l+1),book[str[l++]-'a']--;
    }
    cout<<ans;
}