【每日一题】字符串

解题思路

一个字符串 S 的子串 T 是合法的，当且仅当 T 中包含了所有的小写字母。求所有的合法的 S 的子串中，长度最短是多少。

尺取法：滑动窗口、双指针。
由 和 确定一个区间，表示一个子字符串 T，如果 T 合法，计算此时的子串长度，更新最短长度，将 右移；否则将 右移。

C++代码

#include<iostream>
using namespace std;

int cnt[26];

bool isLegal(){
    for(int i=0; i<26; ++i){
        if(cnt[i] < 1)
            return false;
    }
    return true;
}

int main(){
    string s;
    cin >> s;
    int n = s.size();
    int i = 0;
    int j = 0;
    while(j < n){
        int pos = s[j] - 'a';
        cnt[pos] += 1;
        if(isLegal())
            break;
        ++j;
    }
    int ans = j - i + 1;
    while(i < n && j < n){
        if(isLegal()){
            ans = min(ans, j-i+1);
            int pos = s[i] - 'a';
            cnt[pos] -= 1;
            ++i;
        }
        else{
            ++j;
            if(j == n)
                break;
            int pos = s[j] - 'a';
            cnt[pos] += 1;
        }
    }
    cout << ans << endl;
    return 0;
}