# 340. Longest Substring with At Most K Distinct Characters

## Description

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

## Solutions

• change from 2 to k
• class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
Map<Character, Integer> cnt = new HashMap<>();
int n = s.length();
int ans = 0, j = 0;
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
cnt.put(c, cnt.getOrDefault(c, 0) + 1);
while (cnt.size() > k) {
char t = s.charAt(j);
cnt.put(t, cnt.getOrDefault(t, 0) - 1);
if (cnt.get(t) == 0) {
cnt.remove(t);
}
++j;
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}

• class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
unordered_map<char, int> cnt;
int n = s.size();
int ans = 0, j = 0;
for (int i = 0; i < n; ++i) {
cnt[s[i]]++;
while (cnt.size() > k) {
if (--cnt[s[j]] == 0) {
cnt.erase(s[j]);
}
++j;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};

• class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
cnt = Counter() # or, cnt = defaultdict(int)
ans = i = 0
for j, c in enumerate(s):
cnt[c] += 1
while len(cnt) > k:
cnt[s[i]] -= 1
if cnt[s[i]] == 0:
cnt.pop(s[i])
i += 1
ans = max(ans, j - i + 1)
return ans


• func lengthOfLongestSubstringKDistinct(s string, k int) (ans int) {
cnt := map[byte]int{}
j := 0
for i := range s {
cnt[s[i]]++
for len(cnt) > k {
cnt[s[j]]--
if cnt[s[j]] == 0 {
delete(cnt, s[j])
}
j++
}
ans = max(ans, i-j+1)
}
return
}

• function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
const cnt: Map<string, number> = new Map();
let l = 0;
for (const c of s) {
cnt.set(c, (cnt.get(c) ?? 0) + 1);
if (cnt.size > k) {
cnt.set(s[l], cnt.get(s[l])! - 1);
if (cnt.get(s[l]) === 0) {
cnt.delete(s[l]);
}
l++;
}
}
return s.length - l;
}