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.


Two pointers, Hash table

public int lengthOfLongestSubstringTwoDistinct(String s) {
    if(s == null || s.length() == 0)
        return 0;
    Map<Character, Integer> map = new HashMap<>();
    int b = 0, e = 0, max = 1;
    while(e < s.length()){
        char ce = s.charAt(e);
        map.put(ce, map.getOrDefault(ce, 0) + 1);
        while(map.size() > 2){
            char cb = s.charAt(b);
            int amount = map.get(cb);
            if(-- amount > 0){
                map.put(cb, amount);
            }else map.remove(cb);
            b ++;
        }
        max = Math.max(max, e - b + 1);
        e ++;
    }
    return max;
}

K Distinct Characters

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if(s == null || s.length() == 0 || k == 0)
        return 0;
    Map<Character, Integer> map = new HashMap<>();
    int b = 0, e = 0, max = 1;
    while(e < s.length()){
        char ce = s.charAt(e);
        map.put(ce, map.getOrDefault(ce, 0) + 1);
        while(map.size() > k){
            char cb = s.charAt(b);
            int amount = map.get(cb);
            if(-- amount > 0){
                map.put(cb, amount);
            }else map.remove(cb);
            b ++;
        }
        max = Math.max(max, e - b + 1);
        e ++;
    }
    return max;
}

results matching ""

    No results matching ""