Longest Substring with At Most Two Distinct Characters

• Time:O(n)
• Space:O(128) = O(1)

C++

``````class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int ans = 0;
int distinct = 0;
vector<int> count(128);

for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s[r]] == 1)
++distinct;
while (distinct == 3)
if (--count[s[l++]] == 0)
--distinct;
ans = max(ans, r - l + 1);
}

return ans;
}
};
``````

JAVA

``````class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int ans = 0;
int distinct = 0;
int[] count = new int[128];

for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s.charAt(r)] == 1)
++distinct;
while (distinct == 3)
if (--count[s.charAt(l++)] == 0)
--distinct;
ans = Math.max(ans, r - l + 1);
}

return ans;
}
}
``````

Python

``````class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
ans = 0
distinct = 0
count = [0] * 128

l = 0
for r, c in enumerate(s):
count[ord(c)] += 1
if count[ord(c)] == 1:
distinct += 1
while distinct == 3:
count[ord(s[l])] -= 1
if count[ord(s[l])] == 0:
distinct -= 1
l += 1
ans = max(ans, r - l + 1)

return ans
``````