159.Longest Substring with At Most Two Distinct Characters

  • 41.1%

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.


本题与 第3题,第76题都可以用同一个模板解决。

方法一:

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
vector<int> map(128,0);
int counter=0, begin=0, end=0, d=0;
while(end<s.size()){
if(map[s[end++]]++>0) counter++;
while(counter>0) if(map[s[begin++]]-->1) counter--;
d=max(d, end-begin); //while valid, update d
}
return d;
}

我的代码实现,自己通过测试,但leetcode有锁,无法判断是否通过所有样例

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 Soulution
{
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int n = s.size();
if (n <= 1) return n;
int begin = 0, end = 0, d = 0, counter = 0;
vector<int> indexs(256, 0);
while (end < n) {
if (indexs[s[end]] == 0)
counter++;
indexs[s[end]]++;
end++;
while (counter > 2) {
if (indexs[s[begin]] == 1)
counter--;
indexs[s[begin]]--;
begin++;
}
d = max(d, end - begin);
}
return d;
}
};
谢谢你,可爱的朋友。