There is a string 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 题目大意： 给最长1e6的字符串和k，让你求有多少个子串，每个子串至少包含k个不同的字符。 思路: 尺取：既然让找的每个子串至少包含k个不同的字符，就设两个变量 l和r，从头开始，固定 l，r后移，直到有出现k个不同的子串停止，则 r及右端点后面的不影响该子串，所以从 l开始的满足要求的子串有 n-r+1个，如此遍历每个左端点； 小优化：将没出现过的字符标记一下，出现过则不统计，这样r就可以不用一直从1开始。 ac代码
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e6+7; const ll INF=1e9+7; ll n; char c[maxn]; ll vis[maxn]; int main() { ll t; scanf("%lld",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%s",c); scanf("%lld",&n); ll l=0,r=0; ll len=strlen(c); ll k=0,ans=0; while(l<len) { //r=l; while(r<len&&k<n) { if(vis[c[r]-'a']==0) k++; vis[c[r]-'a']++; r++; } if(k<n) //如果剩下的不同字符少于最少要满足的个数，退出 break; ans+=len-r+1; vis[c[l]-'a']--; if(vis[c[l]-'a']==0) k--; l++; } printf("%lld\n",ans); } return 0; }