Longest Substring with At Most K Distinct Characters - Python Solution

 Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        if n <= k:
            return n
        left,right = 0,0
        max_len = k
        hashmap = collections.defaultdict()
        while right < n:
            # inserting the last index of the distinct elements
            if len(hashmap) <= k:
                hashmap[s[right]] = right
                right+=1
            
            # when we have more than k distinct elements
            #we need to move the left pointer 
            if len(hashmap) == k+1:
                del_idx = min(hashmap.values())
                del hashmap[s[del_idx]]
                left = del_idx+1
            max_len = max(max_len,right-left)
        return max_len   
TC: O(n) SC: O(n)

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...