重新排列

题目

牛牛有个很喜欢的字符串 "puleyaknoi"。

牛牛有 T 个很长很长的字符串，他很喜欢把字符串中的子串（连续的某段）打乱，并且按照自己的喜好重新排列。

如果牛牛能把一段重新排列出他喜欢的字符串，他就会把这个子串称作：喜欢的子串。

求出对于每个字符串，最短的喜欢的子串的长度是多少？

如果没有，请输出-1。

解题思路

双指针 + 滑动窗口

如果区间 [i, j] 内的字符串能排列成喜欢的字符串，向右移动 i，否则向右移动 j。

C++代码

#include<iostream>
#include<cstring>
using namespace std;

int like[26] = {0};
int tmp[26]={0};
string str = "puleyaknoi";

inline bool check(){
    for(int i=0; i<26; ++i){
        if(tmp[i]<like[i])
            return false;
    }
    return true;
}

int main(){
    int T;
    string s;
    for(auto c : str){
        int i = c - 'a';
        like[i] += 1;
    }
    cin >> T;
    while(T--){
        cin >> s;
        memset(tmp, 0, sizeof(tmp));
        int ans = -1;
        int i=0, j=0;
        tmp[s[0]-'a'] += 1;
        while(j<s.size()){
            if(check()){
                if(ans == -1)
                    ans = j-i+1;
                else
                    ans = min(ans, j-i+1);
                tmp[s[i]-'a']-=1;
                ++i;
            }
            else{
                ++j;
                if(j==s.size()) break;
                tmp[s[j]-'a']+=1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}