hdoj String 5672 （字符串模拟）求至少有k个不重复的字符的子串个数

String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1252    Accepted Submission(s): 415

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
        

Source BestCoder Round #81 (div.2) 问题描述

有一个 10\leq10≤长度\leq 1,000,000≤1,000,000 的字符串，仅由小写字母构成。求有多少个子串，包含有至少k(1 \leq k \leq 26)k(1≤k≤26)个不同的字母？      

输入描述

输入包含多组数据. 第一行有一个整数T (1\leq T\leq 10)T(1≤T≤10), 表示测试数据的组数. 对于每组数据:
第一行输入字符串SS。
第二行输入一个整数kk。
      

输出描述

对于每组数据，输出符合要求的子串的个数。      

输入样例

2
abcabcabca
4
abcabcabcabc
3
      

输出样例

0
55      

//思路： 一个模拟题，从第一个字符一直遍历到最后一个，如果在前kk个字符间刚好有k个不相同的字符，那么在此处就不用往后走了，后面的只要逐个加上都是满足题意的，然后再去掉前面的i个字符，看是否还满足前kk个字符之间刚好有k个不同的字符，若满足则kk不用往后走，直接加上相应的长度即可，若不满足，那么kk再往后走，直到找到满足题意的要求后再停止，然后加上相应的后面的后面的长度。 按照这个一直全部遍历一遍后，所得即为所求。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 1000010
using namespace std;
char s[N];
int c[210];
int main()
{
	int t,k,i,j;
	scanf("%d",&t);
	while(t--)
	{		
		scanf("%s%d",s,&k);
		int len=strlen(s);
		ll ans=0;
		int cnt=0,kk=0;
		memset(c,0,sizeof(c));
		for(i=0;i<len;i++)
		{
			if(i)
			{
				c[s[i-1]]--;
				if(!c[s[i-1]])
					cnt--;
			}
			while(cnt<k&&kk<len)
			{
				if(!c[s[kk]])
					cnt++;
				c[s[kk++]]++;
			}
			if(cnt>=k)
				ans+=len-kk+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}