LeetCode Solutions
159. Longest Substring with At Most Two Distinct Characters
Time: $O(n)$ Space: $O(128) = O(1)$
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;
}
};
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;
}
}
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