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

Use the sliding window technique. Pointer j moves faster, pointer i moves slower. Keep moving the right pointer j and record the s[j] characters into the hashmap. When the hashmap has k + 1 distinct character, remove the s[i] character from the map and move i right to one position so that the sliding window contains only k distinct characters.

Python Solution

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

Leave a Reply

Your email address will not be published. Required fields are marked *