Longest Substring with At Most Two Distinct Characters - Python Solution

 Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        k = 3
        n = len(s)
        if n < k:
            return n
        left,right = 0,0
        max_len = 2
        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-1 or 2 distinct elements
            #we need to move the left pointer 
            if len(hashmap) == k:
                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...