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

Link at here.

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
    }
    

All Problems

All Solutions