Question
Formatted question description: https://leetcode.ca/all/340.html
340 Longest Substring with At Most K Distinct Characters
Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2,
T is "ece" which its length is 3.
@tag-string
@tag-2pointers
Algorithm
Same as Longest Substring with At Most Two Distinct Characters
.
- change from 2 to k
Code
Java
-
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; } } }
-
// 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(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