https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
Longest Substring with At Most Two Distinct Characters
Total Accepted: 4982 Total Submissions: 16108 Difficulty: Hard
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is “ece” which its length is 3.
Code
class Solution(object):
def lengthOfLongestSubstringTwoDistinct(self, s):
"""
:type s: str
:rtype: int
"""
end = dict()
max_len = 0
start = 0
for i,c in enumerate(s):
if len(end) <2:
end = i
else: # len(end) == 2
if c in end.keys():
end = i
else:
end_early_c = min(end.keys(), key=lambda x: end[x])
start = end[end_early_c] + 1
end.pop(end_early_c, None)
end = i
l = i - start + 1
if l > max_len:
max_len = l
return max_len
Idea
Use a dictionary `end` to record at which indices the previous two distinct characters are last seen. Then, when a new character appears which are not in `end.keys()`, the substring satisfying our rules can only start after one of the two existing characters, whichever is seen more earlier.
for example, `aaabbbaac`. When you see `c`, you can only start after `bb`.