牛客练习赛70

练习赛70"/>

牛客练习赛70

题目：

牛牛有个很喜欢的字符串”puleyaknoi“。
牛牛有T个很长很长的字符串，他很喜欢把字符串中的子串（连续的某段）打乱，并且按照自己的喜好重新排列。
如果牛牛能把一段重新排列出他喜欢的字符串，他就会把这个子串称作：喜欢的子串。
牛牛是个懒人，他不喜欢对太长的子串进行重排，那样他会觉着眼镜很累。
你能帮他求出对于每个字符串，最短的喜欢的子串的长度是多少吗？
如果没有，请输出-1。

输入：

第一行一个表示数据组数
接下来行每行一个字符串（保证字符串只含小写字母）

输出：

共T行每行一个答案

样例：

输入：

2
sxpuleyaaknoip
konijiwa

输出：

11
-1

思路

用尺取判断和二分判断均可，这里使用二分判断
二分出结果，然后暴力扫一遍看看此时的二分结果是否符合要求即可

AC代码：

#include<stdio.h>
#include<iostream>
#include<map>
#include<queue>
#include<string.h>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;#define ll long longconst int N = 1e5 + 15;
char str[N];
bool check(int len, int k) {map<char, int>mp;for (int j = 0; j < k; j++)mp[str[j]]++;if (mp['p'] != 0 && mp['u'] != 0 && mp['l'] != 0 && mp['e'] != 0 && mp['y'] != 0 && mp['a'] != 0 && mp['k'] != 0 && mp['n'] != 0 && mp['o'] != 0 && mp['i'] != 0)return true;for (int i = k; i < len; i++) {mp[str[i - k]] -= 1;mp[str[i]]++;if (mp['p'] != 0 && mp['u'] != 0 && mp['l'] != 0 && mp['e'] != 0 && mp['y'] != 0 && mp['a'] != 0 && mp['k'] != 0 && mp['n'] != 0 && mp['o'] != 0 && mp['i'] != 0)return true;}return false;
}
int main()
{int t; scanf("%d", &t);while (t--) {scanf("%s", str);int len = strlen(str);map<char, int>mp;for (int i = 0; i < len; i++)mp[str[i]]++;int nn = 0;if (mp['p'] != 0 && mp['u'] != 0 && mp['l'] != 0 && mp['e'] != 0 && mp['y'] != 0 && mp['a'] != 0 && mp['k'] != 0 && mp['n'] != 0 && mp['o'] != 0 && mp['i'] != 0)nn = 1;else {printf("-1\n");continue;}int l = 0, r = len;while (l < r) {int mid = (l + r) / 2;if (check(len, mid))r = mid;elsel = mid + 1;}printf("%d\n", l);}return 0;
}