Welcome to Subscribe On Youtube

340. Longest Substring with At Most K Distinct Characters

Description

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

Solutions

Same as 159 Longest Substring with At Most Two Distinct Characters

  • change from 2 to k
  • 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;
        }
    }
    
  • class Solution {
    public:
        int lengthOfLongestSubstringKDistinct(string s, int k) {
            unordered_map<char, int> cnt;
            int n = s.size();
            int ans = 0, j = 0;
            for (int i = 0; i < n; ++i) {
                cnt[s[i]]++;
                while (cnt.size() > k) {
                    if (--cnt[s[j]] == 0) {
                        cnt.erase(s[j]);
                    }
                    ++j;
                }
                ans = max(ans, i - j + 1);
            }
            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
    
    
  • 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
    }
    
  • function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
        const cnt: Map<string, number> = new Map();
        let l = 0;
        for (const c of s) {
            cnt.set(c, (cnt.get(c) ?? 0) + 1);
            if (cnt.size > k) {
                cnt.set(s[l], cnt.get(s[l])! - 1);
                if (cnt.get(s[l]) === 0) {
                    cnt.delete(s[l]);
                }
                l++;
            }
        }
        return s.length - l;
    }
    
    

All Problems

All Solutions