159. Longest Substring with At Most Two Distinct Characters
Sliding window. Time = O(n), Space = O(1) since additional space is used only for a hashmap with at most 3 elements.
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int i = 0;
int j = 0;
int longest = 0;
Map<Character, Integer> map = new HashMap<>();
while (j < s.length()) {
char jChar = s.charAt(j);
if (map.containsKey(jChar)) {
map.put(jChar, map.get(jChar) + 1);
} else {
map.put(jChar, 1);
}
j++;
while (map.size() > 2) {
char iChar = s.charAt(i);
if (map.containsKey(iChar) && map.get(iChar) > 1) {
map.put(iChar, map.get(iChar) - 1);
} else {
map.remove(iChar, 1);
}
i++;
}
longest = Math.max(longest, j - i);
}
return longest;
}
}