340. Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.

Constraints:

  • 1 <= s.length <= 5 * 104
  • 0 <= k <= 50

Solution

 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

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] map = new int[128];
        int start = 0;
        int end = 0;
        int maxLen = 0;
        int counter = 0;
        while (end < s.length()) {
            char c = s.charAt(end);
            if (map[c] == 0) counter++;
            map[c]++;
            end++;
            while (counter > k) {
                char prev = s.charAt(start);
                if (map[prev] == 1) counter--;
                map[prev]--;
                start++;
            }
            
             maxLen = Math.max(maxLen, end - start);
        }
        
        return maxLen;
    }
}

Solution 2021-09-07

 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
30
31
32
33
34
35
36

class Solution {
    /*
    eceba
    01234
    1223
    
    */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] freq = new int[256];
        int max = 0;
        int n = s.length();
        int start = 0;
        int end = 0;
        int counter = 0;
        while (end < n) {
            char c = s.charAt(end);
            freq[c]++;
            if (freq[c] == 1) {
                counter++;
            }
            end++;
            while (counter > k) {
                char prev = s.charAt(start);
                freq[prev]--;
                if (freq[prev] == 0) {
                    counter--;
                }
                
                start++;
            }
            max = Math.max(end - start, max);
        }
        
        return max;
    }
}

Solution 2021-11-21

 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

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int lo = 0;
        int hi = 0;
        int n = s.length();
        int[] freq = new int[256];
        int count = 0;
        int max = 0;
        while (hi < n) {
            freq[s.charAt(hi)]++;
            if (freq[s.charAt(hi)] == 1) { 
                count++;
            }
            while (count > k) {
                freq[s.charAt(lo)]--;
                if (freq[s.charAt(lo)] == 0) { 
                    count--;
                }
                lo++;
            }
            max = Math.max(max, hi - lo + 1);
            hi++;
        }
        return max;
    }
}