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 * 10⁴
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
}

340 - Longest Substring with At Most K Distinct Characters

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions