LeetCode: Longest Substring with At Most K Distinct Characters

LeetCode: 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.isEmpty() || k < 1) return 0;
        if (s.length() <= k) return s.length();

        int result = k;
        int pre = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);

            while (map.size() > k) {
                char p = s.charAt(pre++);
                int count = map.get(p) - 1;
                if (count == 0) {
                    map.remove(p);
                } else {
                    map.put(p, count);
                }
            }
            result = Math.max(result, i - pre + 1);
        }
        return result;
    }
}