386 · 最多有k个不同字符的最长子字符串 描述

给定字符串S，找到最多有k个不同字符的最长子串T。

样例

样例 1:

输入: S = "eceba" 并且 k = 3
输出: 4
解释: T = "eceb"

样例 2:

输入: S = "WORLD" 并且 k = 4
输出: 4
解释: T = "WORL" 或 "ORLD"

挑战

O(n) 时间复杂度

public class Solution {
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if(k==0) return 0;
        Map<Character,Integer> map = new HashMap();
        int i=0,j=0;
        int max = 0;
        while(j<s.length()){
            char c = s.charAt(j);
            int count = map.getOrDefault(c,0);
            if(count==0 && map.size()>=k){
                max = Math.max(max,j-i);
                while(map.size()>=k){
                    char t = s.charAt(i);
                    int temp = map.get(t);
                    if( temp==1 ) map.remove(t);
                    else map.put(t,temp-1);
                    i++;
                }
            }
            map.put(c,count+1);
            j++;
        }
        max = Math.max(max,j-i);
        return max;
    }
}

FollowUp: 如果你拿到的是一个Stream, 而不是有限长度的String, 如何解决？