题目：

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.

链接： 

题解：

跟"Longest Substring Without Repeating Characters"很像。碰到这种题目依然是考虑使用Sliding Window来解决，只不过要多考虑用什么样的数据结构来存储数据。

这里有几种方法，第一种是用HashSet<Character>来保存字符，从头到尾扫描字符串，当set.size() >= 2并且当前字符为新字符，我们从当前字符的前一个字符s.charAt(i - 1)从后向前查找，碰到不同于s.charAt(i - 1)的字符在位置j时，设置index为j + 1，尝试更新max。假如要扩展到n个distinct characters的话，我们就需要另外设置一个counter，来记录反向查找时一种经历了多少种字符。

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {    public int lengthOfLongestSubstringTwoDistinct(String s) {      //sliding window        if(s == null || s.length() < 3)            return s.length();                Set
     
       set = new HashSet<>();        int max = 0, index = 0;                                 // use index to record left bar of window                for(int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if(!set.contains(c)) {                if(set.size() >= 2) {                    for(int j = i - 1; j >= 0; j--)             // scan from i - 1 to 0                        if(s.charAt(j) != s.charAt(i - 1)) {                            set.remove(s.charAt(j));                            index = j + 1;                            break;                        }                }                 set.add(c);            }            max = Math.max(i - index + 1, max);        }                return max;    }}
     

 

第二种可以用HashMap<Character，Integer>来存储字符以及字符最后一次出现的lastIndex。这样碰到map.size() >= 2而且要添加新字符的时候，我们只需要查找到map.keySet里不同于上一字符s.charAt(i - 1)的那个entry，设置index为entry.val + 1即可，接下来继续尝试更新max。 max与第一种方法一样，为Math.max(i - index + 1, max)。扩展到n个distinct character的话，要对lastIndex做个排序，然后按照倒序找到需要溢出的字符，设置index，再更新max。

Time Complexity - O(n)，Space Complexity - O(1)。

public class Solution {    public int lengthOfLongestSubstringTwoDistinct(String s) {      //sliding window        if(s == null || s.length() < 3)            return s.length();        HashMap
     
       map = new HashMap<>();       // use map to record 
      
               int max = 0, index = 0;                                 // use index to record left bar of window                for(int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if(!map.containsKey(c)) {                if(map.size() >= 2) {                    Set
       
         keys = map.keySet();                                        for(Character key : keys)               // find char different from lastChar                        if(key != s.charAt(i - 1)) {                            index = map.get(key) + 1;                            map.remove(key);                            break;                        }                }             }            map.put(c, i);            max = Math.max(i - index + 1, max);        }                return max;    }}
       
      
     

 

第三种可以不用Set以及Map来存储，反正只要求两个不同字符，可以设置几个变量，也能有一样的效果。

 

 

Reference：

https://leetcode.com/discuss/19261/my-java-ac-solution

https://leetcode.com/discuss/21929/share-my-c-solution

https://leetcode.com/discuss/22980/java-solution-for-k-unique-characters

https://leetcode.com/discuss/31292/clean-11-lines-ac-answer-o-1-space-o-n-time

https://leetcode.com/discuss/54294/java-sliding-window-solution-fast