Longest Substring with At Most Two Distinct Characters

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.


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


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.


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
Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

In a binary min heap, the maximum element can be found in:

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Implementation

Not Sure What to Study? Take the 2-min Quiz:

In a binary min heap, the minimum element can be found in:

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫