340. Longest Substring with At Most K Distinct Characters

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

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

Solution:

Exactly the same problem with Longest Substring with At Most Two Distinct Characters.



Code:

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int start = 0;
        int end = 0;
        int count = 0;
        while (end < s.length()) {
            char c = s.charAt(end);
            if (!map.containsKey(c)) {
                map.put(c, 1);
            }
            else {
                map.put(c, map.get(c) + 1);
            }
            if (map.get(c) == 1) {
                count++;
            }
            end++;
            while (count > k) {
                char ch = s.charAt(start);
                map.put(ch, map.get(ch) - 1);
                if (map.get(ch) == 0) {
                    count--;
                }
                start++;
            }
            max = Math.max(max, end - start);
        }
        return max;
    }
}