05 August 2008
Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
Example 1:
1
2
3
Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.
Example 2:
1
2
3
Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.
所有滑动窗口的题目的总结在这里。维护一个hashmap，保存字符和其位置索引，通过判断其size来确定现在滑动窗口有几个字符，如果大于2个，则找到最左边的位置索引删除，同时保存最大子字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null && s.length() == 0) {
return -1;
}
int slow = 0, fast = 0;
int maxLength = 0;
HashMap<Character, Integer> map = new HashMap<>();
while (fast < s.length()) {
if (map.size() <= 2) {
map.put(s.charAt(fast), fast);
fast++;
}
if (map.size() > 2) {
int leftMost = s.length();//初始值只要不是在0到s.length()-1之间就行
for (int i : map.values()) {
leftMost = Math.min(leftMost, i);
}
char toBeDeleted = s.charAt(leftMost);
map.remove(toBeDeleted);
slow = leftMost + 1;//删除的字符的下一个
}
maxLength = Math.max(maxLength, fast - slow);
}
return maxLength;
}
}
另外一种写法，比较高效但不好扩展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
char[] tree = s.toCharArray();
int result = 0;
int[] basket = {-1, -1};
for(int i = 0; i < tree.length; i++){
if(basket[0] == -1){
basket[0] = i;
}
if(basket[1] == -1){
basket[1] = i;
}else if(tree[i] != tree[basket[1]] && tree[i] != tree[basket[0]]){
basket[1] = i;
int j = i - 1;
while(j > 0 && tree[j - 1] == tree[j]){//从i前面一个数字开始查找，直到找到不同的字符（因为滑动窗口最多两个字符u）
j--;
}
basket[0] = j;
}
result = Math.max(result, i - Math.min(basket[0], basket[1]) + 1);
}
return result;
}
}