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