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

340 - Longest Substring with At Most K Distinct Characters

Question

Algorithm

Code

All Problems

All Solutions