Longest Substring with At Most Two Distinct Characters
给一个字符串s, 求最长子字符串, 里面包含最多两个不同的字符. 用两个指针left和right, 分别标记符合的子字符串的左边和右边, 找的时候, 用一个map存每个字符出现的最右的位置, 这样就可以知道如何移动左边.
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int n = s.length();
if(n < 3)
return n;
int left = 0;
int right = 0;
int res = 0;
Map<Character, Integer> m = new HashMap<>();
while(right < n) {
if(m.size() < 3){
m.put(s.charAt(right),right);
right++;
}
if(m.size() == 3){
int min = Integer.MAX_VALUE;
for(int v : m.values())
min = Math.min(min, v);
m.remove(s.charAt(min));
left = min + 1;
}
res = Math.max(res, right - left);
}
return res;
}
}