题解 | 游游的字母子串

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String str = sc.next();

        int lenMax = 0;

        int[] count = new int[26];  // 统计不同的单词
        int left = 0, mount = 0;

        for (int right = 0; right < n; right++){
            char c = str.charAt(right);
            if(count[c - 'a'] == 0){        // 如果这个单词第一次出现，则次数加一
                mount++;
            }
            count[c - 'a']++;
            while(mount > k){       // 如果单词种类大于规定的k，则需要移动左指针
                char leftChar = str.charAt(left);
                count[leftChar - 'a']--;
                if(count[leftChar - 'a'] == 0){
                    mount--;
                }
                left++;
            }

            lenMax = Math.max(lenMax, right - left + 1);

        }

        System.out.println(lenMax);
    }
}

这是一道经典的滑动窗口题目，在不超过单词种类的情况下求最长字串

第一步：如果出现新的单词了（count[c - 'a'] == 0），种类mount需要加一，其他情况不需要加一

第二步：如果种类超过了要求的种类个数k，则需要移动左指针，收缩窗口，左指针对应的单词在count[]数组肯定存在，需要减一，如果这个单词减完之后为0，证明这个种类的单词已经不存在了，对应的种类减一；