Longest Substring At most k
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
- Time: O(n)
- Space: O(1)
public int lengthOfLongestSubstringAtMost(String s) {
int[] count = new int[256];
int distinct = 0, maxLen = 0, j = 0;
for (int i = 0; i < s.length(); i++) {
if (count[s.charAt(i)] == 0)
distinct++;
count[s.charAt(i)]++;
while (distinct > 2) {
count[s.charAt(j)]--;
if (count[s.charAt(j)] == 0) {
distinct--;
}
j++;
}
maxLen = Math.max(i - j + 1, maxLen);
}
return maxLen;
}