HDOJ5672

字符串的新姿势新技能解锁：HDOJ5672

给定一个串长不超过1e6的字符串，统计其中子串中不同字母个数不小于k的子串总数

遇到这种题，肯定只能用O（n）的算法扫描一遍：姿势要好才能AC

如果从0到m刚好包括k个字符，那么0到m+1也有，0到len-1也有，总数为len-1-m+1=len-m个值

如果第0个字符在1-m的区间中存在，那么1-m子串也是符合题意的，同理1到m+1也有，1到len-1也有，总数为len-m-1个值

如果第1个字符在2-m的区间中存在……

所以，只需要一次扫描，并且判定端点的值是不是在之后的区间中存在即可

int main(){
	//input;
	scanf("%d",&t);
	while(t--){
		scanf("%s%d",s,&k);
		int len=strlen(s);
		int sum=0,head=0;
		long long ans=0;
		memset(num,0,sizeof(num));
		for(int i=0;i<len;i++){
			if (!num[s[i]-'a']) sum++;
			num[s[i]-'a']++;
			while(sum>=k){
				ans+=len-i;
				num[s[head]-'a']--;
				if (!num[s[head]-'a']) sum--;
				head++;
			}
		}
		//注意需要longlong变量 
		cout<<ans<<endl;
	}
	return 0;
}