博文中会简要介绍Leetcode P0159题目分析及解题思路。
“Longest Substring with At Most Two Distinct Characters”这道题是一道非常经典的滑动窗口的题目，同时也是一道原型题的简化版。原型题是问最多k个不同的字符的最长子串，而这里则是问2个。其实这道题在解法上和原型题基本一致，所以所谓的简化其实也就是把k替换为了k=2而已。
Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
这道题的思路其实比较简单，核心思路在于确定滑动窗口滑动的条件，即左右指针移动的条件。具体的移动条件如下，
首先我们要使用一个HashTable来存储已经访问的字符和其个数，
1. 若当前访问的字符出现过，或者第一次出现且窗口内的不同字符种类的个数小于2个，那么如果出现过，则在HashTable中增加计数，若没有出现过，则在HashTable中添加新的Key并且更新字符种类计数器。然后向右移动指针。
2. 若当前字符没有出现过且窗口内不同字符的种类个数已经有2个了，那么记录最大值后，将左指针向左移动来减少多余的字符，知道新增加的那个种类的字符被删除。然后重新调整字符种类计数器。
以下是Java的题解代码实现。
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s.length() == 0)
return 0;
Map<Character, Integer> char2CountMap = new HashMap<>();
char[] chars = s.toCharArray();
int left = 0, right = 0, distinct = 0, maxLen = 0, L = chars.length;
while (right < L) {
char ch = chars[right];
// More than 2 distinct characters
if (char2CountMap.getOrDefault(ch, 0) == 0 && distinct > 1) {
maxLen = Math.max(maxLen, right-left);
char2CountMap.put(chars[left], char2CountMap.get(chars[left])-1);
while (char2CountMap.get(chars[left]) > 0) {
++left;
char2CountMap.put(chars[left], char2CountMap.get(chars[left])-1);
}
// Keep distinct
++left;
--distinct;
}
else {
int count = char2CountMap.getOrDefault(ch, 0);
char2CountMap.put(ch, count+1);
if (count == 0)
++distinct;
++right;
}
}
maxLen = Math.max(maxLen, right-left);
return maxLen;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int L = s.length();
if (L == 0)
return 0;
unordered_map<char, int> char2count;
int left = 0, right = 0, distinct = 0, max_len = 0;
while (right < L) {
// Expand until more than 2 disctinct character
while (right < L && distinct <= 2) {
++char2count[s[right]];
if (char2count[s[right]] == 1)
++distinct;
++right;
}
if (distinct <= 2)
return max(max_len, right-left);
max_len = max(max_len, right-1-left);
// Shorten until the substring is valid
--char2count[s[left]];
while (char2count[s[left]] > 0) {
++left;
--char2count[s[left]];
}
++left;
--distinct;
}
max_len = max(max_len, right-left);
return max_len;
}
};