# Question

Formatted question description: https://leetcode.ca/all/340.html

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

# Algorithm

Same as Longest Substring with At Most Two Distinct Characters.

• change from 2 to k

# Code

• import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Longest_Substring_with_At_Most_K_Distinct_Characters {
public static void main(String[] args) {
Longest_Substring_with_At_Most_K_Distinct_Characters out = new Longest_Substring_with_At_Most_K_Distinct_Characters();
Solution_arrayAsMap s = out.new Solution_arrayAsMap();

System.out.println(s.lengthOfLongestSubstringKDistinct("eceba", 2));
}

public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k <= 0) {
return 0;
}

// char => its count in window
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0;
int left = 0;
int right = 0;

for (right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}

// if distinct chars more than k
if (map.size() > k) {
maxLen = Math.max(maxLen, right - left);

// Shrink the window size
while (map.size() > k) { // can be done by another counter variable
char leftChar = s.charAt(left);
int freq = map.get(leftChar);
if (freq == 1) {
map.remove(leftChar); // @note: remove by key
} else {
map.put(leftChar, freq - 1);
}
left++;
}
}
}

// @note: final check
if (left < s.length()) {
maxLen = Math.max(maxLen, right - left);
}

return maxLen;
}
}

public class Solution_arrayAsMap {

public int lengthOfLongestSubstringKDistinct(String s, int k) {

int[] countMap = new int[256];
Set<Character> hs = new HashSet<>();

int result = 0;
int left = 0;
int right = 0;

while (right < s.length()) {

char c = s.charAt(right);
countMap[c]++;

if (hs.size() > k) {

result = Math.max(result, right - left);

while (hs.size() > k) {
if (--countMap[s.charAt(left)] == 0) {
hs.remove(s.charAt(left));
}
left++;
}
}

right++;
}

// @note: final check
if (left < s.length()) {
result = Math.max(result, right - left);
}

return result;
}

}
}

############

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;
}
}

• // OJ: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int cnt[128] = {}, distinct = 0, i = 0, j = 0, ans = 0, N = s.size();
while (j < N) {
distinct += cnt[s[j++]]++ == 0;
while (distinct > k) distinct -= --cnt[s[i++]] == 0;
ans = max(ans, j - i);
}
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

############

class Solution(object):
def lengthOfLongestSubstringKDistinct(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
j = 0
ans = 0
dict = {}
for i in range(len(s)):
dict[s[i]] = dict.get(s[i], 0) + 1
while j <= i and len(dict) > k:
dict[s[j]] -= 1
if dict[s[j]] == 0:
del dict[s[j]]
j += 1
ans = max(ans, i - j + 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
}

func max(a, b int) int {
if a > b {
return a
}
return b
}