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

Link at here.

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
    
    

All Problems

All Solutions