Tuesday, January 31, 2017

Leetcode/G家 -- 159. Longest Substring with At Most Two Distinct Characters(window 2 ptr)

159. Longest Substring with At Most Two Distinct Characters (window 2 ptr)
Hard
https://leetcode.com/problems/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.
思路: Use window method, counter to track distinct character, when counter > 2, remove one distinct character(till count = 0) to track next substring.

public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, end = 0;
        int counter = 0, len = 0;
        while(end < s.length()){
            char cur = s.charAt(end);
            if(!map.containsKey(cur)) map.put(cur, 0);
            map.put(cur, map.get(cur) + 1);
            if(map.get(cur) == 1) counter++;//new distinct char
            while(counter > 2){//
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) - 1);
                if(map.get(c2) == 0) counter--;
                start++;
            }
            len = Math.max(end - start + 1, len);
            end++;
        }
        return len;
    }

No comments:

Post a Comment