Description
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
Example 1:
Input: "eceba" Output: 3 Explanation: tis "ece" which its length is 3.
Example 2:
Input: "ccaabbb" Output: 5 Explanation: tis "aabbb" which its length is 5.
Explanation
sliding window
Python Solution
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
max_length = 0
visited = {}
i = 0
j = 0
while j < len(s):
c = s[j]
if c in visited:
visited[c] = visited[c] + 1
else:
visited[c] = 1
if len(visited) > 2:
max_length = max(max_length, j - i)
while len(visited) > 2:
t = s[i]
count = visited[t]
if count > 1:
visited[t] = count -1
else:
del visited[t]
i += 1
j += 1
return max(max_length, len(s) - i)
- Time Complexity: ~N
- Space Complexity: ~1
where N is a number of characters in the input string.