HDU -5672 String（尺取法）

String

Problem Description
There is a string S.S only contain lower case English character.(10≤length(S)≤1,000,000)
How many substrings there are that contain at least k(1≤k≤26) distinct characters?

Input
There are multiple test cases. The first line of input contains an integer T(1≤T≤10) indicating the number of test cases. For each test case:

The first line contains string S.
The second line contains a integer k(1≤k≤26).

Output
For each test case, output the number of substrings that contain at least k dictinct characters.

Sample Input
2
abcabcabca
4
abcabcabcabc
3

Sample Output
0
55

从前往后遍历，统计新出现的字母，若达到k个，则后面的再往上加都满足(ans+=l-r)，然后去掉前i个字符看还有没有k个不同的字符，若有，加上相应的长度，若没有，继续往后遍历

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char s[1000200];
int vis[30]={0};
int main()
{
int t, k;
scanf("%d", &t);
while(t--)
{
scanf("%s%d", s, &k);
int sum=0, len=strlen(s), r=0;
long long ans=0;
for(int i=0; i<len; i++)
{
while(sum<k&&r<len)
{
vis[s[r]-'a']++;
if(vis[s[r]-'a']==1)//统计不同的字符
sum++;
r++;
}
if(sum==k)//加上后面的长度
ans+=len-r+1;
vis[s[i]-'a']--;//去掉前i个字符
if(vis[s[i]-'a']==0)//若这个字符是唯一的，sum--
sum--;
}
printf("%lldn", ans);
}
return 0;
}

最后

以上就是年轻毛巾为你收集整理的HDU -5672 String（尺取法）的全部内容，希望文章能够帮你解决HDU -5672 String（尺取法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。