December 22, 2019

159. Longest Substring with At Most Two Distinct Characters

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;
    }
}
comments powered by Disqus