String HDU 5672(双指针)

String HDU 5672(双指针)

传送门

题意：一个字符串中找到所有拥有不少于k个不同的字符的子串。

import java.io.*;
import java.util.*;public class Main {
static final int N = 1000005;
    static final int inf= 0x3f3f3f3f;
    static final double eps= 1e-5;
    static int vis[]=new int[27];
    static char a[]=new char[N];
    public static void main(String[] args){
    Scanner cin = new Scanner(new InputStreamReader(System.in));
    int T=cin.nextInt();
    while(0!=T--){
    String s=cin.next();
    int k=cin.nextInt();
    a=s.toCharArray();
    int l=0,r=0,len=s.length(),cnt=0;
    long ans=0;
    Arrays.fill(vis,0);
    while(l<=r&&l<len){   //注意是l<len，即使r到了末端，还可以形成很多子串
    while(r<len&&cnt<k){
    if(vis[a[r]-'a']==0){
    cnt++;
    }
    vis[a[r]-'a']++;
    r++;
    }
    if(cnt==k){
    ans+=len-r+1;
    }
    if(l<=r)
    {
vis[a[l]-'a']--;
if(vis[a[l]-'a']==0){
cnt--;
}
l++;
}
    }
    System.out.println(ans);
    }
    cin.close();
    }
}