重新排列
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format:
%lld
题目描述
牛牛有个很喜欢的字符串”puleyaknoi“。
牛牛有T个很长很长的字符串，他很喜欢把字符串中的子串（连续的某段）打乱，并且按照自己的喜好重新排列。
如果牛牛能把一段重新排列出他喜欢的字符串，他就会把这个子串称作：喜欢的子串。
牛牛是个懒人，他不喜欢对太长的子串进行重排，那样他会觉着眼镜很累。
你能帮他求出对于每个字符串，最短的喜欢的子串的长度是多少吗？
如果没有，请输出-1。
输入描述:
第一行一个表示数据组数
接下来行每行一个字符串（保证字符串只含小写字母）
输出描述:
共T行每行一个答案
示例1
输入
复制
2
sxpuleyaaknoip
konijiwa
输出
复制
11
-1
说明
sxpuleyaaknoip中puleyaaknoi可以重排成puleyaknoia，其中包含有puleyaknoi。
konijiwa不能重新排列出puleyaknoi，所以是-1
备注:
T≤10,字符串长度不超过10^5
题解：
题意很明确，我们来分析一下，我们所要找的满足条件的区间没有办法一下确定，也就是这个区间是需要不断调整的，因为找到一个区间满足条件后，有可能不是最简情况，还能再缩，所以我们可以采用尺取法
我们一开始确定左边界L=0，然后不断更新右边界r，直到r满足条件，这样就确定了一个区间，记录答案，然后左边界L右移一位，然后右边界在原先的基础上找满足情况的区间，更新区间最小值，这样一直循环，我们找到了所有满足情况的区间，并取得最小值，所以找到最优解
记得L右移动一位时，将原本L位置的数据删除，因为原L的数已经不在现区间里了
详细看代码
代码：
#include<bits/stdc++.h>
using namespace std;
string w="puleyaknoi";
const int maxn=1e5+9;
int a[maxn]={
0};
int b[maxn]={
0};
const int INF=1e6+9;
bool check()
{
for(int i=0;i<26;i++)
{
if(b[i]&&a[i]<b[i])
return 0;
}
return 1;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<=w.length();i++)
{
b[w[i]-'a']++;
}
while(n--)
{
string s;
cin>>s;
int l,r,tot=INF;
for(l=0,r=0;l<s.length();l++)
{
while(check()==0&&r<s.length())
{
a[s[r]-'a']++;
r++;
}
if(check())
{
tot=min(tot,r-l);
}
a[s[l]-'a']--;
}
if(tot==INF)cout<<"-1"<<endl;
else cout<<tot<<endl;
}
}
京公网安备 11010502036488号