This problem can be efficiently solved using a sliding window approach. The core idea is to maintain a window within the string s
that contains at most two distinct characters. We expand the window as long as it satisfies this condition, and update the maximum length found so far. If the window contains more than two distinct characters, we shrink it from the left until the condition is met again.
Algorithm:
Initialization: We use a hash map (dictionary in Python) cnt
to store the frequency of each character within the current window. Two pointers, i
(left) and j
(right), define the window's boundaries. ans
stores the maximum length found.
Expansion: The right pointer j
iterates through the string. For each character s[j]
, we increment its count in cnt
.
Contraction: If the number of distinct characters in cnt
(using len(cnt)
in Python, cnt.size()
in Java/C++, or len(cnt)
in Go) exceeds 2, we need to shrink the window. The left pointer i
moves forward, decrementing the count of s[i]
in cnt
. If the count of s[i]
becomes 0 after decrementing, we remove it from cnt
. We repeat this contraction until cnt
has at most two distinct characters.
Update Maximum: After each expansion or contraction, we update ans
with the maximum length of the current window (i - j + 1
).
Return: Finally, ans
contains the length of the longest substring with at most two distinct characters.
Time Complexity: O(N), where N is the length of the string. Each character is visited and processed at most twice (once during expansion and once during contraction).
Space Complexity: O(1). The hash map cnt
stores at most two distinct characters, so its space usage is constant regardless of the input string's size. (Technically, the space usage is O(min(N, 26)) as we may need to store all 26 characters in the worst case. However, we can assume the number of unique characters is limited in the problem setting, hence O(1)).
Code Explanation (Python):
from collections import Counter
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
cnt = Counter() # Frequency counter for characters in the window
ans = j = 0 # Initialize max length and right pointer
for i, c in enumerate(s): # Efficient iteration using enumerate
cnt[c] += 1 # Add the current character to the window
while len(cnt) > 2: # Shrink the window if more than 2 distinct chars
cnt[s[j]] -= 1 # Decrement the leftmost character's count
if cnt[s[j]] == 0: #Remove from counter if count becomes zero
del cnt[s[j]]
j += 1 # Move left pointer
ans = max(ans, i - j + 1) #Update the maximum length
return ans
The other languages (Java, C++, Go) follow the same logic, adapting the syntax and data structures to each language. For example, in Java, HashMap
is used instead of Counter
, and cnt.size()
replaces len(cnt)
. The core algorithm remains the same.