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.

解法1：O(N)

滑动窗口的解法。
C++

1

Java

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
27
28
29
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        HashMap<Character, Integer> map = new HashMap<>();
        int count = 0, start = 0, end = 0;
        int res = 0;
        while (end < s.length()) {
            char current = s.charAt(end);
            map.put(current, map.getOrDefault(current, 0) + 1);
            if (map.get(current) == 1) {
                count++;
            }
            end++;  // move 1 position forward
            while (count > k) {
                char prev = s.charAt(start);
                map.put(prev, map.get(prev) - 1);
                if (map.get(prev) == 0) {
                    count--;
                }
                start++;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}