340. Longest Substring with At Most K Distinct Characters

Published on February 24, 2024

Question

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

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

Approach

Sliding window when the question is asking something for substring;
The logic is clear
1. Start from left , if in the map then it will not affect the unique number count so we move forward ;
2. If it's not in the map, then we put into map, but we monitor the map , while the map size if larger than k, we move left forward and move out elements , update their count in the map, until the unique number count(size of map) is k

Code

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0, j = 0; j < s.length(); j++) {
            Character ch = s.charAt(j);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch) + 1);
                res = Math.max(res, j - i + 1);
            } else {
                map.put(ch, 1);
                while (map.size() > k) {
                    Character ch_i = s.charAt(i);
                    int count = map.get(ch_i);
                    if (count == 1) {
                        i++;
                        map.remove(ch_i);
                    } else {
                        map.put(ch_i, map.get(ch_i) - 1);
                        i++;
                    }
                }
                res = Math.max(res, j - i + 1);
            }
        }
        return res;
    }
}