LeetCode [340] Longest Substring with At Most K Distinct Characters

340. Longest Substring with At Most K Distinct Characters

Hard

Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int lengthOfLongestSubstringKDistinct(string s, int k) { int counts[256] = {0}; int sz = s.size(), start = 0, distincts = 0, ret = 0; for(int e=0; e<sz; ++e) { if(counts[s[e]]==0) distincts++; counts[s[e]]++; if(distincts>k) { while(counts[s[start]]) { if(--counts[s[start]] == 0) break; start++; } start++; distincts--; } ret = max(ret, e-start+1); } return ret; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public int lengthOfLongestSubstringKDistinct(String s, int k) { int n = s.length(), i = 0, j = 0, longest = 0, d = 0; Map<Character, Integer> map = new HashMap<>(); while(j<n){ char cur = s.charAt(j++); if(map.getOrDefault(cur, 0)==0) d++; map.put(cur, (map.getOrDefault(cur, 0)+1)); while(d>k){ char last = s.charAt(i++); map.put(last, map.get(last)-1); if(map.get(last)==0) d--; } longest = Math.max(longest, j-i); } return longest; } }