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

Tag: Array/List, Sliding Window

Key Points:

1. A typical sliding window problem with a right pointer keep moving and left pointer jumps under certain condition
2. Maintain a hashmap to track the status of the current substring between left and right.
   1. The most intuitive hashmap definition is “character → number of occurrences”
   2. A more efficient one is “character → rightmost index of the char”

Solution:

# HashMap Definition 1: “character → number of occurrences”
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
		if not s:
        return 0
	  map = dict() # char -> count
	  max_len = 0
	  left = 0 # Substring will be between left and right,inclusive
	  right = 0
	  while right < len(s):
	      c = s[right]
	      # char has been in the substring
	      if c in map: 
	          map[c] += 1
	          max_len = max(max_len, right - left + 1)
	          right+=1
	      else: # char is a new char
	          # current substring has less than 2 char:
	          if len(map) < 2:
	              map[c] = 1
	              max_len = max(max_len, right - left + 1)
	              right+=1
	          # current substring has 2 different chars
	          else:
	              # process char from left until substring has only one char
	              while len(map) == 2: 
	                  left_c = s[left]
	                  map[left_c] -= 1
	                  left += 1
	                  if map[left_c] == 0:
	                      del map[left_c]
	              map[c] = 1
	              max_len = max(max_len, right - left + 1)
	              right += 1
     return max_len

 #Hashmap Definition 2: character -> rightmost index of the char
 def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
	   if not s:
	   return 0
   map = dict() # char -> right most index
   max_len = 0
   left = 0
   right = 0
   while right < len(s):
        c = s[right]
        if c in map or len(map) < 2:
            map[c] = right # update the index of char to the rightmost one
            max_len = max(max_len, right - left + 1)
            right += 1
        else: # current substring has 2 different chars
            rm_char_idx = min(map.values()) # find the idx of char to remove
            rm_char = s[rm_char_idx]
            del map[rm_char]
            map[c] = right
            left = rm_char_idx + 1 # left pointer jumps directly to the new index
            max_len = max(max_len, right - left + 1)
            right += 1
    return max_len