最多包含k个不同字符的最长子串

题目

实现函数：输入一个字符串str，一个int值k，输出str中最多含有k个字符的子串最大长度.例如str="aabc"，k="2"，则输出3，因为最长含2个字符的子串是"aab"

解决

1. 暴力法
   i遍历字符串，考察以i开头的子串满足条件的最大长度，时间复杂度为O(n^2)
2. 暴力法
   遍历str的所有子串（从长到短），考察其是否满足条件，时间复杂度为O(n^2)
3. HashMap+快慢指针
   利用map记录子串中每个字符的数量、利用快慢指针进行遍历，分别代表子串的结尾j与开头i
   快指针将指向的字符计入map，若此时map.size>k，则移动慢指针（砍掉子串的开头），直至map.size()恢复正常，快指针继续向前（增加子串的结尾）。这一过程中j-i+1的最大值即为答案

代码

public static int find(String str, int k){
        HashMap<Character,Integer> map = new HashMap<>();
        int max = 0;
        for (int j=0,i=0;j<str.length();j++){
            char toPut = str.charAt(j);
            map.put(toPut,map.getOrDefault(toPut, 0)+1);
            while (map.size()>k){
                char temp = str.charAt(i);
                map.put(temp, map.get(temp)-1);//利用map键唯一的特点，通过put实现值修改
                if (map.get(temp)==0)
                    map.remove(temp);
                i ++;
            }
            max = Math.max(max,j-i+1);
        }
        return max;
    }