Welcome to Subscribe On Youtube
159. Longest Substring with At Most Two Distinct Characters
Description
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 <= 10^{5}
s
consists of English letters.
Solutions
This problem is solved using the sliding window technique alongside a counter (from collections
module) to keep track of the frequency of each character within the current window. Here’s a breakdown of how the code works:
Code Breakdown:
 Initialization:
cnt
: ACounter
object (which could also be adefaultdict(int)
from thecollections
module) used to track the number of occurrences of each character within the current window of the string.ans
: An integer variable used to store the length of the longest valid substring found so far.i
: An integer variable used as the start index of the current window. Initially set to 0.
 Main Loop:
 The code iterates over the string
s
withenumerate
, which provides both the indexj
and the characterc
at that index.  For each character
c
, its count is incremented incnt
.  If the window (from
i
toj
) contains more than two distinct characters (len(cnt) > 2
), the code enters awhile
loop to shrink the window from the left until it contains at most two distinct characters. This is done by: Decreasing the count of the character at the start of the window (
s[i]
).  If the count of
s[i]
becomes 0, it means this character is no longer in the current window, so it is removed fromcnt
.  Incrementing
i
to shrink the window from the left.
 Decreasing the count of the character at the start of the window (
 The code iterates over the string
 Update Answer:
 After possibly shrinking the window to ensure it contains at most two distinct characters,
ans
is updated to be the maximum of its current value and the length of the current window (j  i + 1
).
 After possibly shrinking the window to ensure it contains at most two distinct characters,
 Return:
 After iterating through the entire string, the function returns
ans
, which holds the length of the longest substring containing at most two distinct characters.
 After iterating through the entire string, the function returns
Example:
Consider s = "eceba"
:
 When
j = 2
(s[0:3] = "ece"
), the window contains two distinct characters, soans
is updated to 3.  When
j = 3
(s[0:4] = "eceb"
), the window now has three distinct characters. The innerwhile
loop shrinks the window to"ceb"
, andans
remains 3.  The process continues until the end of the string, with the window being adjusted as necessary to ensure it never contains more than two distinct characters.

class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { Map<Character, Integer> cnt = new HashMap<>(); int n = s.length(); int ans = 0; for (int i = 0, j = 0; i < n; ++i) { char c = s.charAt(i); cnt.put(c, cnt.getOrDefault(c, 0) + 1); while (cnt.size() > 2) { char t = s.charAt(j++); cnt.put(t, cnt.get(t)  1); if (cnt.get(t) == 0) { cnt.remove(t); } } ans = Math.max(ans, i  j + 1); } return ans; } }

class Solution { public: int lengthOfLongestSubstringTwoDistinct(string s) { unordered_map<char, int> cnt; int n = s.size(); int ans = 0; for (int i = 0, j = 0; i < n; ++i) { cnt[s[i]]++; while (cnt.size() > 2) { cnt[s[j]]; if (cnt[s[j]] == 0) { cnt.erase(s[j]); } ++j; } ans = max(ans, i  j + 1); } return ans; } };

''' >>> from collections import Counter >>> c = Counter() >>> c Counter() >>> c['a'] += 1 >>> c Counter({'a': 1}) >>> c Counter({'a': 1, 'c': 1, 'b': 1}) >>> c.pop(2) Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 2 >>> >>> c.pop('c') 1 >>> c Counter({'a': 1, 'b': 1}) ''' from collections import Counter class Solution: def lengthOfLongestSubstringTwoDistinct(self, s: str) > int: cnt = Counter() # or, cnt = defaultdict(int) ans = i = 0 for j, c in enumerate(s): cnt[c] += 1 while len(cnt) > 2: # shrink cnt[s[i]] = 1 if cnt[s[i]] == 0: cnt.pop(s[i]) i += 1 ans = max(ans, j  i + 1) return ans

func lengthOfLongestSubstringTwoDistinct(s string) (ans int) { cnt := map[byte]int{} j := 0 for i := range s { cnt[s[i]]++ for len(cnt) > 2 { cnt[s[j]] if cnt[s[j]] == 0 { delete(cnt, s[j]) } j++ } ans = max(ans, ij+1) } return }