LeetCode Longest Substring with At Most Two Distinct Characters Solution

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

Constraints:

  • 1 <= s.length <= 105
  • s consists of English letters.

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



Solution

Since we don't know the size of the window, we will apply the flexible sliding window template. We will keep a last_occurrence hashmap that stores the last occurence of a character in the current window. Every time the right pointer reaches a new character, we update that character's last occurrence to r. In every iteration, we will check whether the current window is longer than max_len. This means that whenever the window becomes invalid, we must update the window first before the check. We will update l when condition(window) evaluates to true. Here, condition(window) is when the hashmap contains three characters. We must discard the entirety of one character c, which means we will choose the smaller last_occurrence[c] to maintain a longers substring. So the new left pointer is updated to min(last_occurrence.values())+1 and we will delete this character from the last_occurrence hashmap.

Implementation

1def lengthOfLongestSubstringTwoDistinct(self, s):
2    last_occurrence = dict()
3    max_len, l = 0, 0
4    for r in range(len(s)):
5        last_occurrence[s[r]] = r
6        r += 1
7        if len(last_occurrence) == 3:
8            l = min(last_occurrence.values())+1
9            del last_occurrence[s[l-1]]
10        max_len = max(max_len, r - l)
11    return max_len