jiandanchiqu

Description

      小明最近迷恋上了字符串，于是发明了k-子串问题。k-子串问题是指，给定一个字符串s，是否存在一个子串，使得该子串包含的字母a~z均为k个。

Input

输入测试组数T，每组测试数据输入两行，第一行是整数n (26<=n<=100000)和k(1<=k<=n/26),分别表示字符串的长度和k-子串，第二行是一个长度为n的字符串s，字符串s仅包含a~z的26种小写字母

Output

若存在这样的子串，则输出YES，否则输出NO

Sample Input

226 1abcdefghijklmnopqrstuvwxyz26 1abcdefghijklmnopqrstuvwxyy

Sample Output

YESNO

HINT

       子串： 对于字符串长度为n的字符串，下标为0,1,…,n-1, 子串是指一段连续的下标L,L+1,…,R(0<=L<=R<n)所对应的字符串，例如abc，那么子串有a,b,c,ab,bc,abc        输入数据量较大，建议使用scanf/printf #include<cstdio> #include<string.h> using namespace std; char words[100005]; int ans[1000]; int main() { int T; scanf("%d",&T); while(T--){ int n,k; scanf("%d%d",&n,&k); memset(words,0,sizeof(words)); memset(ans,0,sizeof(ans)); scanf("%s",words); int p=0; //start int cnt = 0; int flag = 0; for(int i=0;i<n;i++){ //end int temp = words[i]; if(ans[temp] < k){ ans[temp]++; if(ans[temp]==k){ cnt++; } } else{ for(int j=p;j<i;j++){ int t = words[j]; ans[t]--; if(ans[t] == k-1){ cnt--; } if(words[j] == words[i]){ cnt++; ans[t]++; p = j+1; break; } } } if(cnt == 26){ printf("YES\n"); flag = 1; break; } } if(flag != 1){ printf("NO\n"); } } return 0; }