Difficulty: Hard
More:【目录】LeetCode Java实现
Description
Given a string S, find the length of the longest substring T that contains at most two distinct characters.
For example,
Given S = “eceba”,
T is "ece" which its length is 3.
Intuition
方法一：假设有一个滑动窗口，窗口左右两边的下标分别记为left和right。遍历字符串，依次确定left和right。具体实现见代码（稍微难理解一点）
方法二：还是引入一个滑动窗口，窗口左右两边的下标分别记为left和right。再引入一个numDistinct变量，用于记录窗口中已经出现的不同字符次数。此外，使用一个int[258]来模拟哈希表，记录每个字符出现的次数count。
遍历字符串（right右移），当遇到的字符出现次数为0时，numDistinct++; 当numDistinct的次数超过2时，说明left需要往右移，在left往右移的过程中，减少所指字符的count，最终使得numDistinct=2，才暂停left的右移。
方法二容易理解，且可以用于求解k个不同字符组成的最长子字符。下面代码中方法二就是实现k个不同字符的情况。
Solution
//Method1: Longest Substring with At Most Two Distinct Characters
public static int lengthOfLongestSubstringTwoDistinct1(String s) {
if(s==null || s.length()<=0)
return 0;
int left=0;
int right=-1;
int maxLen=0;
for(int i=1;i<s.length();i++) {
if(s.charAt(i)==s.charAt(i-1)) continue;
if(right!=-1 && s.charAt(i)!=s.charAt(right)) {
maxLen=Math.max(maxLen, i-left);
left=right+1;
}
right=i-1;
}
return Math.max(s.length()-left,maxLen);
} //Method2: Longest Substring with At Most k Distinct Characters
public static int lengthOfLongestSubstringTwoDistinct2(String s,int k) {
if(s==null || s.length()<=0)
return 0;
int[] count=new int[256];
int numDistinct=0;
int maxLen=0;
int left=0;
for(int right=0;right<s.length();right++) {
if(count[s.charAt(right)]==0) numDistinct++;
count[s.charAt(right)]++;
while(numDistinct>k) {
count[s.charAt(left)]--;
if(count[s.charAt(left)]==0) numDistinct--;
left++;
}
maxLen=Math.max(maxLen, right-left+1);
}
return maxLen;
}
Complexity
Time complexity : O(n)
Space complexity : O(1)
What I've learned
1. 方法一中，i可能会越界，所以代码第16行别忘记了s.length()-left。
2. 方法一里的left，right以及 i指针之间的关系要搞清楚。
3.方法二中引入了numDistinct，非常方便，有时候往往多设置一个变量，就能实现所需要的功能
More:【目录】LeetCode Java实现