Leetcode: 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.

方法一：用HashMap, map里面存元素及其出现次数。维护一个最大长度。用两个指针，右指针一直走到出现3个dinstinct character为止。然后调整左指针删元素，直接从左往右逐个字符的删除，一直删到某个字符不会再出现。判断字符被删光就看次数是否减为了0.

采用方法：

 1 public class Solution {
 2     public int lengthOfLongestSubstringTwoDistinct(String s) {
 3         if (s==null || s.length()==0) return 0;
 4         HashMap<Character, Integer> map = new HashMap<Character, Integer>();
 5         int longest = 0;
 6         int l = 0;
 7         int r = 0;
 8         while (r < s.length()) {
 9             // move right edge
10             char c = s.charAt(r);
11             map.put(c, map.getOrDefault(c, 0) + 1);
12             
13             // move left edge when necessary to make window valid again
14             while (map.size() >= 3 && l <= r) {
15                 char d = s.charAt(l);
16                 if (map.get(d) > 1) map.put(d, map.get(d)-1);
17                 else map.remove(d);
18                 l++;
19             }
20             
21             // calculate the longest window
22             longest = Math.max(longest, r - l + 1);
23             r ++;
24         }
25         return longest;
26     }
27 }

这里每个元素都会进入窗口一次，最多出窗口一次，所以平摊在每个元素上的时间复杂度是O(1)，总时间复杂度为O(N)

Method 2: window never shrink, can possibly be faster