Given a strings, find the length of the longest substring T that contains at most k distinct characters.

Have you met this question in a real interview?

Yes

Example

For example, Given s ="eceba",k = 3,

T is"eceb"which its length is4.

同样通过保持一个从第一个指针到第二个指针的窗口，并且通过hashmap来判断当前有多少不同的元素

注意窗口条件是要找到最后一个满足的，所以一定要停在最后一个满足的地方，在更新答案时不能包括第一个使答案不满足的地方

public class Solution {
    /**
     * @param s : A string
     * @return : The length of the longest substring 
     *           that contains at most k distinct characters.
     */

    //f[n] represents till the nth char the maximum length of substring that less than k diff char

    // f[n] = f[n - 1]
    //
    //sliding windows

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0) {
            return 0;
        }
        int ans = 0;
        int i = 0;
        int j = 0;

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (i = 0; i < s.length(); i++) {
            while (j < s.length()) {

                if (map.containsKey(s.charAt(j))) {
                    map.put(s.charAt(j), map.get(s.charAt(j)) + 1);
                } else {
                    if (map.size() == k) {
                        break;
                    }
                    map.put(s.charAt(j), 1);
                }
                j++;



            }
            ans = Math.max(ans, j - i);


            map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
            if (map.get(s.charAt(i)) == 0) {
                map.remove(s.charAt(i));
            }
        }
        return ans;
    }




    /*
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // write your code here
        if (s == null || k <= 0) {
            return 0;
        }

        int start = 0;
        int end = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        while (end < s.length()) {
            if (map.containsKey(s.charAt(end))) {
                map.put(s.charAt(end), map.get(s.charAt(end)) + 1);
                end++;
                maxLength = Math.max(maxLength, end - start);
                continue;
            } 

            if (!map.containsKey(s.charAt(end)) && map.size() < k) {
                map.put(s.charAt(end), 1);
                end++;
                maxLength = Math.max(maxLength, end - start);
                continue;
            }

            map.put(s.charAt(start), map.get(s.charAt(start)) - 1);
            if (map.get(s.charAt(start)) == 0) {
                map.remove(s.charAt(start));
            }
            maxLength = Math.max(maxLength, end - start);
            start++;

        }

        return maxLength;



    }
    */

}