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

(1) Java

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

(2) Python

(3) Scala