LeetCode 159. Longest Substring with At Most Two Distinct Characters

Description

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

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: tis "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.

Explanation

sliding window

Python Solution

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:        
        max_length = 0        
        visited = {}
        
        i = 0
        j = 0
        while j < len(s):
            c = s[j]
            
            if c in visited:
                visited[c] = visited[c] + 1
            else:
                visited[c] = 1
                
            if len(visited) > 2:                
                max_length = max(max_length, j - i)
                
                while len(visited) > 2:
                    t = s[i]
                    count = visited[t]
                    if count > 1:
                        visited[t] = count -1
                    else:
                        del visited[t]
                    i += 1
            j += 1
                                            
        return max(max_length, len(s) - i)
            

• Time Complexity: ~N
• Space Complexity: ~1

where N is a number of characters in the input string.