滑动窗口(三)——Longest K unique charac

题目:

Given a string you need to print the size of the longest possible substring that has exactly k unique characters. If there is no possible substring print -1.
Example
For the string aabacbebebe and k = 3 the substring will be cbebebe with length 7.

Input:
The first line of input contains an integer T denoting the no of test cases then T test cases follow. Each test case contains two lines . The first line of each test case contains a string s and the next line conatains an integer k.

Output:
For each test case in a new line print the required output.

Constraints:
1<=T<=100
1<=k<=10

Example:
Input:
2
aabacbebebe
3
aaaa
1
Output:
7
4

代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class GFG {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-->0){
            String str = br.readLine();
            int k = Integer.parseInt(br.readLine());
            int len = str.length();
            int [] arr = new int[26];
            int dis=0;
            int start=0;
            int maxLen=-1;
            for(int i=0;i<len;i++){
                if(arr[str.charAt(i)-'a']==0){
                    dis++;
                }
                arr[str.charAt(i)-'a']++;
                while(dis>k){
                    arr[str.charAt(start)-'a']--;
                    if(arr[str.charAt(start)-'a']==0){
                        dis--;
                    }
                    start++;
                }
                if(dis==k&&maxLen<i-start+1){
                    maxLen=i-start+1;
                }
            }
            System.out.println(maxLen);
        }
    }
}

分析:

这道题和滑动窗口(二)有点像,但比它稍微复杂点,首先也是用个arr存同种类的字符,然后滑动窗口,不同的是,这里如果匹配不到k个不同字符串,则输出-1,所以处理与前一篇略有不同.

时间复杂度同样是O(N)