159. Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

Solution:

Use two pointers to form a window.

Use the end pointer point to go through the string.

For each element, add it to a HashMap and update its frequency.

When we find an element has frequency 1, we increase count by 1.

When count > 2, it means there are more than 2 distinct characters.

So we remove elements from the start pointer.

If its frequency become 0, we know this unique character is removed. We decrease the count by 1.

In the loop, we use a max variable to keep an updated max length of the valid window.



Code:

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int start = 0;
        int end = 0;
        int count = 0;
        while (end < s.length()) {
            char c = s.charAt(end);
            if (!map.containsKey(c)) {
                map.put(c, 1);
            }
            else {
                map.put(c, map.get(c) + 1);
            }
            if (map.get(c) == 1) {
                count++;
            }
            end++;
            while (count > 2) {
                char ch = s.charAt(start);
                map.put(ch, map.get(ch) - 1);
                if (map.get(ch) == 0) {
                    count--;
                }
                start++;
            }
            max = Math.max(max, end - start);
        }
        return max;
    }
}