Welcome to Subscribe On Youtube
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]++; hs.add(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 }