LeetCode 340. Longest Substring with At Most K Distinct Characters

Description

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

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

Explanation

Have a hashmap to record the number of the occurrence of the visited characters. Pointer j moves faster, pointer i moves slower. Keep moving the right pointer as long as the number of visited distinct characters is no greater than k. Move the slower pointer to the right and reduce the number of characters the slow pointer points in hashmap.

Python Solution

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        
        if k == 0:
            return 0
        
        result = 0
        counter = {}            
        j = 0
        
        
        for i in range(len(s)):            
            while j < len(s) and (len(counter) < k or (len(counter) == k and s[j] in counter)):
                counter[s[j]] = counter.get(s[j], 0) + 1
                
                j += 1
                
            if len(counter) <= k:
                result = max(result, j - i)
            
            counter[s[i]] -= 1
            
            if counter[s[i]] == 0:
                del counter[s[i]]
            
        return result
    
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.