c**z
发帖数: 669 | 1 given a string ,return the longest substring that contains at most two
characters.
该咋写？ |
t********e
发帖数: 344 | 2 Two pointer traversal + memorization. 这类题目是不是都差不多这样 |
f*******w
发帖数: 1243 | 3 和leetcode的Longest Substring Without Repeating Characters类似
两个指针start和end，从左往右扫一遍，如果start和end之间符合条件就++end，否则
就++start |
l*****a
发帖数: 14598 | 4 我去替你onsite吧
【在 c**z 的大作中提到】
: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？
|
v******l
发帖数: 60 | 5 我电面的时候问了这题，记录一下那个turning point 就好 |
M*****M
发帖数: 20 | 6 类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
unordered_map 记录这2个char最后出现的index。
string findsubstring(string s) {
if(s.empty()) {
return string();
}
queue que;
unordered_map map;
int maxlen = 0, maxindex=0, index=0;
for(int i=0; i
if(map.find(s[i])==map.end()) {
if(que.size()==2) {
if(i-index>maxlen) {
maxlen = i-index;
maxindex = index;
}
//update que and map
char c=que.front();
que.pop();
index = map[c]+1;
map.erase(c);
}
map[s[i]] = i;
que.push(s[i]);
} else {
map[s[i]] = i;
}
}
if(s.size()-index>maxlen) {
maxlen = s.size()-index;
maxindex = index;
}
return s.substr(maxindex, maxlen);
} |
i**********u
发帖数: 119 | 7 如果问你一个character你就会，问两个就不会了？是不是第二天就被据了：）
开个玩笑啊 别怒 |
j*****d
发帖数: 1625 | 8 at most two
characters.。什么意思？2个不一样的？aaaaab算longest是么？ |
s**********r
发帖数: 8153 | |
a*******e
发帖数: 455 | 10 没看懂， string 里除了字符 都是空格？
【在 c**z 的大作中提到】
: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？
|
|
|
w*****t
发帖数: 485 | 11 这个空间复杂度高了，会要求你不用额外数据结构来解决。
这题 corner case多
【在 M*****M 的大作中提到】
: 类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
: unordered_map 记录这2个char最后出现的index。
: string findsubstring(string s) {
: if(s.empty()) {
: return string();
: }
: queue que;
: unordered_map map;
: int maxlen = 0, maxindex=0, index=0;
: for(int i=0; i
|
p********n
发帖数: 165 | 12 O(1) space complexity.
O(n) time complexity.
// Given a string, return the longest substring that contains at most // two
characters.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}
int first_start = 0;
int second_start;
char first = input[0];
char second;
int end = 1;
while (end < input.size() && input[end] == first) {
end++;
}
if (end == input.size()) {
return input.size();
} else {
second = input[end];
second_start = end;
}
int solution = end - first_start + 1;
while (end < input.size() - 1) {
end++;
if (input[end] == first || input[end] == second) {
solution = (end - first_start + 1) > solution ?
(end - first_start + 1) : solution;
} else {
first = second;
first_start = second_start;
second = input[end];
second_start = end;
}
}
return solution;
}
int main() {
string input1 = "aabcdeffzzeee";
string input2 = "abababa";
cout << "solution length == "<< FindLength(input2) << endl;
return 0;
} |
y**********a
发帖数: 824 | 13 int longestTwoCharWindow(String s) {
if (s.length()==0) return 0;
char c1=s.charAt(0),c2=c1;
int ct=1,ml=1,rec=1;
for (int l=0,r=1;r
if (ct==1)
if (s.charAt(r)==c1)++rec;
else {++ct;rec=1;c2=s.charAt(r);}
else if (ct==2)
if (s.charAt(r)==c1){rec=1;}
else if (s.charAt(r)==c2){++rec;}
else {l=r-rec;rec=1;c1=c2;c2=s.charAt(r);}
ml=Math.max(ml, r-l);
}
return ml;
} |
p********n
发帖数: 165 | 14 Space O(1)
Time O(n)
// Given a string, return the longest substring that contains at most // two
characters.
// solution: scan the string and update the first and second letter's last
occurrence
// indices, and update the solution's start index.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}
int solu_start = 0;
int first_end, second_end;
char first = input[0];
char second;
int curr = 1;
while (curr < input.size() && input[curr] == first) {
curr++;
}
if (curr == input.size()) {
return input.size();
} else {
first_end = curr - 1;
second = input[curr];
second_end = curr;
}
int solution = curr - solu_start + 1;
while (curr < input.size() - 1) {
curr++;
if (input[curr] == first) {
first_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else if (input[curr] == second) {
second_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else { // look back to last curr
if (input[curr - 1] == first) {
solu_start = second_end + 1;
second = input[curr];
second_end = curr;
} else {
solu_start = first_end + 1;
first = input[curr];
first_end = curr;
}
}
}
return solution;
}
int main() {
string input1 = "aabcdeffzzeee";
string input2 = "ababa";
string input3 = "ababacccccc";
cout << "solution length == "<< FindLength(input3) << endl;
return 0;
} |
i******d
发帖数: 7 | 15 Space O(1), Time O(n)
public int maxLength(String s){
if (s.isEmpty()) return 0;
int diffCharIndex = -1, currentLength = 1, maxLength = 1;
for (int i = 1; i < s.length(); i++)
{
if (s.charAt(i) != s.charAt(i-1))
{
if (diffCharIndex == -1 || s.charAt(i) == s.charAt(
diffCharIndex)) {
currentLength++; diffCharIndex = i - 1; }
else { currentLength = i - diffCharIndex; diffCharIndex = i-
1; }
}
else currentLength++;
if (currentLength > maxLength) maxLength = currentLength;
}
return maxLength;
} |
a*****y
发帖数: 22 | 16 int FindLongsetTwoLetterSubstr(const std::string& str) {
int max_len = 0;
int curr_len = 0;
int n = str.size();
if (n == 0) {
return 0;
}
char letters[2];
letters[0] = str[0];
int i = 0;
int last_pos = 0;
for (; i < n; ++i) {
if (i != 0 && str[i] != str[i - 1]) {
letters[1] = str[i];
last_pos = i;
break;
}
}
int org_pos = 0;
for (; i < n; ++i) {
if (str[i] != str[i - 1]) {
if (str[i] != letters[0] && str[i] != letters[1]) {
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
curr_len = i - last_pos;
org_pos = last_pos;
last_pos = i;
if (str[org_pos] == letters[0]) {
letters[1] = str[i];
} else {
letters[0] = str[i];
}
} else {
last_pos = i;
}
}
}
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
return max_len;
} |
s******6
发帖数: 57 | 17 两个指针
int longestSubstr(string s) {
int count[256];
memset(count, 0, sizeof(count));
int cnt = 0;
int i = 0;
int res = 0;
for(int j=0; j
count[s[j]] ++;
if(count[s[j]] == 1) cnt ++;
while(cnt > 2) {
count[s[i]] --;
if(count[s[i]] == 0) cnt --;
i ++;
}
res = max(res, j-i+1);
}
return res;
} |
s******6
发帖数: 57 | 18 就是两个指针+一个计数的，假设是string是 acsii
int longestSubstr(string s) {
int count[256];
memset(count, 0, sizeof(count));
int cnt = 0;
int i = 0;
int res = 0;
for(int j=0; j
count[s[j]] ++;
if(count[s[j]] == 1) cnt ++;
while(cnt > 2) {
count[s[i]] --;
if(count[s[i]] == 0) cnt --;
i ++;
}
res = max(res, j-i+1);
}
return res;
} |
m*****k
发帖数: 731 | 19 counter用不着吧，sliding window idea,
public static int getLongestSubStringWith2Chars(String s) {
if(s==null || s.isEmpty()){
return 0;
}
int c1Idx = 0;
int c2Idx = 0;
int c3Idx = 0;
int l = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) != s.charAt(c2Idx)) {
c3Idx = i;
int temp = c3Idx - c1Idx;
if (temp > l) {
l = temp;
System.out.format("length:%d start:%d end:%d\n", l,
c1Idx, c3Idx - 1);
}
c1Idx = c2Idx;
c2Idx = c3Idx;
}
}
c3Idx = s.length();
int temp = c3Idx - c1Idx;
if (temp > l) {
l = temp;
System.out.format("length:%d start:%d end:%d\n", l, c1Idx,
c3Idx - 1);
}
return l;
}
/**********test********/
@Test
public void testGetLongestSubStringWith2Chars() {
String s = "";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 0);
s = null;
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 0);
s = "abaaab";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 4);
s = "abcaaabbb";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 6);
s = "aaaaabbbbbcdeff";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 10);
} |
Q*****a
发帖数: 33 | 20 string LongestMostTwoSubString(string s) {
printf("s.size():%dn", s.size());
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
for (;;) {
while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (--charCounts[s[start]] != 2) ++start;
++start;
++end;
}
return s.substr(maxStart, maxLen);
}
int main() {
string ss[] = {"", "abcdefgh", "abcdefghabcdefgh", "
abcdefghabcdefghabcdefghijklmnopqrst"};
for (auto s: ss) {
printf("%sn", LongestMostTwoSubString(s).c_str());
}
return 0;
}
【在 c**z 的大作中提到】
: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？
|
|
|
t*******i
发帖数: 4960 | 21 不错，这个一改就可以适用于任何 N 个的情况
【在 Q*****a 的大作中提到】
: string LongestMostTwoSubString(string s) {
: printf("s.size():%dn", s.size());
: // assume char in s are all ASCII, otherwise we can unsigned char and
: 256 slots
: vector charCounts(128, 0);
: int maxStart = 0;
: int maxLen = 0;
: int start = 0, end = 0;
: for (;;) {
: while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;
|
m*****k
发帖数: 731 | 22 sally216 的简洁，一改就可以适用于任何 N 个的情况
【在 t*******i 的大作中提到】
: 不错，这个一改就可以适用于任何 N 个的情况
|
s***n
发帖数: 11 | 23 re
【在 m*****k 的大作中提到】
: sally216 的简洁，一改就可以适用于任何 N 个的情况
|
p********n
发帖数: 165 | 24 sally 的写法要扫2遍 ， 快index一遍， 慢index一遍, 但可以扩展到n个letter.
其他算法有的只要扫一遍。 |
Q*****a
发帖数: 33 | 25 这个偶审题错误，原题是要求如同aaaaabbb这样最多不超过两个不一样的字符构成的子
串，我理解成如abcdabcd这种每个字符出现最多不超过两次。代码没有sally216的简洁
，不过个人习惯解这种区间问题的时候这么写了。顺便鄙视一下买买提的发文超时，居
然没有在session里保存，辛苦敲了半天的东西都没了。telnet时代就有的功能居然都
没实现。
string LongestMostTwoCharsSubString(string s) {
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
int uniqCharCounts = 0;
for (;;) {
for (;end < s.size(); ++end) {
if (++charCounts[s[end]] == 1) ++uniqCharCounts;
if (uniqCharCounts > 2) break;
}
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (uniqCharCounts > 2) {
if (--charCounts[s[start]] == 0) {
--uniqCharCounts;
break;
}
++start;
}
++start;
++end;
}
return s.substr(maxStart, maxLen);
}
【在 t*******i 的大作中提到】
: 不错，这个一改就可以适用于任何 N 个的情况
|
o****s
发帖数: 143 | 26 这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
挪动i指针往后吧。
比如说aabbcd， 应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
先移动i到b，这样res变成3了
【在 s******6 的大作中提到】
: 就是两个指针+一个计数的，假设是string是 acsii
: int longestSubstr(string s) {
: int count[256];
: memset(count, 0, sizeof(count));
: int cnt = 0;
: int i = 0;
: int res = 0;
: for(int j=0; j: count[s[j]] ++;
: if(count[s[j]] == 1) cnt ++;
|
m*****k
发帖数: 731 | 27 aabb时res就是4了
【在 o****s 的大作中提到】
: 这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
: 挪动i指针往后吧。
: 比如说aabbcd， 应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
: 先移动i到b，这样res变成3了
|
j**********3
发帖数: 3211 | |
c**z
发帖数: 669 | 29 given a string ,return the longest substring that contains at most two
characters.
该咋写？ |
t********e
发帖数: 344 | 30 Two pointer traversal + memorization. 这类题目是不是都差不多这样 |
|
|
f*******w
发帖数: 1243 | 31 和leetcode的Longest Substring Without Repeating Characters类似
两个指针start和end，从左往右扫一遍，如果start和end之间符合条件就++end，否则
就++start |
l*****a
发帖数: 14598 | 32 我去替你onsite吧
【在 c**z 的大作中提到】
: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？
|
v******l
发帖数: 60 | 33 我电面的时候问了这题，记录一下那个turning point 就好 |
M*****M
发帖数: 20 | 34 类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
unordered_map 记录这2个char最后出现的index。
string findsubstring(string s) {
if(s.empty()) {
return string();
}
queue que;
unordered_map map;
int maxlen = 0, maxindex=0, index=0;
for(int i=0; i
if(map.find(s[i])==map.end()) {
if(que.size()==2) {
if(i-index>maxlen) {
maxlen = i-index;
maxindex = index;
}
//update que and map
char c=que.front();
que.pop();
index = map[c]+1;
map.erase(c);
}
map[s[i]] = i;
que.push(s[i]);
} else {
map[s[i]] = i;
}
}
if(s.size()-index>maxlen) {
maxlen = s.size()-index;
maxindex = index;
}
return s.substr(maxindex, maxlen);
} |
i**********u
发帖数: 119 | 35 如果问你一个character你就会，问两个就不会了？是不是第二天就被据了：）
开个玩笑啊 别怒 |
j*****d
发帖数: 1625 | 36 at most two
characters.。什么意思？2个不一样的？aaaaab算longest是么？ |
s**********r
发帖数: 8153 | |
a*******e
发帖数: 455 | 38 没看懂， string 里除了字符 都是空格？
【在 c**z 的大作中提到】
: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？
|
w*****t
发帖数: 485 | 39 这个空间复杂度高了，会要求你不用额外数据结构来解决。
这题 corner case多
【在 M*****M 的大作中提到】
: 类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
: unordered_map 记录这2个char最后出现的index。
: string findsubstring(string s) {
: if(s.empty()) {
: return string();
: }
: queue que;
: unordered_map map;
: int maxlen = 0, maxindex=0, index=0;
: for(int i=0; i
|
y**********a
发帖数: 824 | 40 int longestTwoCharWindow(String s) {
if (s.length()==0) return 0;
char c1=s.charAt(0),c2=c1;
int ct=1,ml=1,rec=1;
for (int l=0,r=1;r
if (ct==1)
if (s.charAt(r)==c1)++rec;
else {++ct;rec=1;c2=s.charAt(r);}
else if (ct==2)
if (s.charAt(r)==c1){rec=1;}
else if (s.charAt(r)==c2){++rec;}
else {l=r-rec;rec=1;c1=c2;c2=s.charAt(r);}
ml=Math.max(ml, r-l);
}
return ml;
} |
|
|
p********n
发帖数: 165 | 41 Space O(1)
Time O(n)
// Given a string, return the longest substring that contains at most // two
characters.
// solution: scan the string and update the first and second letter's last
occurrence
// indices, and update the solution's start index.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}
int solu_start = 0;
int first_end, second_end;
char first = input[0];
char second;
int curr = 1;
while (curr < input.size() && input[curr] == first) {
curr++;
}
if (curr == input.size()) {
return input.size();
} else {
first_end = curr - 1;
second = input[curr];
second_end = curr;
}
int solution = curr - solu_start + 1;
while (curr < input.size() - 1) {
curr++;
if (input[curr] == first) {
first_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else if (input[curr] == second) {
second_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else { // look back to last curr
if (input[curr - 1] == first) {
solu_start = second_end + 1;
second = input[curr];
second_end = curr;
} else {
solu_start = first_end + 1;
first = input[curr];
first_end = curr;
}
}
}
return solution;
}
int main() {
string input1 = "aabcdeffzzeee";
string input2 = "ababa";
string input3 = "ababacccccc";
cout << "solution length == "<< FindLength(input3) << endl;
return 0;
} |
i******d
发帖数: 7 | 42 Space O(1), Time O(n)
public int maxLength(String s){
if (s.isEmpty()) return 0;
int diffCharIndex = -1, currentLength = 1, maxLength = 1;
for (int i = 1; i < s.length(); i++)
{
if (s.charAt(i) != s.charAt(i-1))
{
if (diffCharIndex == -1 || s.charAt(i) == s.charAt(
diffCharIndex)) {
currentLength++; diffCharIndex = i - 1; }
else { currentLength = i - diffCharIndex; diffCharIndex = i-
1; }
}
else currentLength++;
if (currentLength > maxLength) maxLength = currentLength;
}
return maxLength;
} |
a*****y
发帖数: 22 | 43 int FindLongsetTwoLetterSubstr(const std::string& str) {
int max_len = 0;
int curr_len = 0;
int n = str.size();
if (n == 0) {
return 0;
}
char letters[2];
letters[0] = str[0];
int i = 0;
int last_pos = 0;
for (; i < n; ++i) {
if (i != 0 && str[i] != str[i - 1]) {
letters[1] = str[i];
last_pos = i;
break;
}
}
int org_pos = 0;
for (; i < n; ++i) {
if (str[i] != str[i - 1]) {
if (str[i] != letters[0] && str[i] != letters[1]) {
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
curr_len = i - last_pos;
org_pos = last_pos;
last_pos = i;
if (str[org_pos] == letters[0]) {
letters[1] = str[i];
} else {
letters[0] = str[i];
}
} else {
last_pos = i;
}
}
}
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
return max_len;
} |
Q*****a
发帖数: 33 | 44 string LongestMostTwoSubString(string s) {
printf("s.size():%dn", s.size());
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
for (;;) {
while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (--charCounts[s[start]] != 2) ++start;
++start;
++end;
}
return s.substr(maxStart, maxLen);
}
int main() {
string ss[] = {"", "abcdefgh", "abcdefghabcdefgh", "
abcdefghabcdefghabcdefghijklmnopqrst"};
for (auto s: ss) {
printf("%sn", LongestMostTwoSubString(s).c_str());
}
return 0;
}
【在 c**z 的大作中提到】
: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？
|
t*******i
发帖数: 4960 | 45 不错，这个一改就可以适用于任何 N 个的情况
【在 Q*****a 的大作中提到】
: string LongestMostTwoSubString(string s) {
: printf("s.size():%dn", s.size());
: // assume char in s are all ASCII, otherwise we can unsigned char and
: 256 slots
: vector charCounts(128, 0);
: int maxStart = 0;
: int maxLen = 0;
: int start = 0, end = 0;
: for (;;) {
: while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;
|
m*****k
发帖数: 731 | 46 sally216 的简洁，一改就可以适用于任何 N 个的情况
【在 t*******i 的大作中提到】
: 不错，这个一改就可以适用于任何 N 个的情况
|
s***n
发帖数: 11 | 47 re
【在 m*****k 的大作中提到】
: sally216 的简洁，一改就可以适用于任何 N 个的情况
|
p********n
发帖数: 165 | 48 sally 的写法要扫2遍 ， 快index一遍， 慢index一遍, 但可以扩展到n个letter.
其他算法有的只要扫一遍。 |
Q*****a
发帖数: 33 | 49 这个偶审题错误，原题是要求如同aaaaabbb这样最多不超过两个不一样的字符构成的子
串，我理解成如abcdabcd这种每个字符出现最多不超过两次。代码没有sally216的简洁
，不过个人习惯解这种区间问题的时候这么写了。顺便鄙视一下买买提的发文超时，居
然没有在session里保存，辛苦敲了半天的东西都没了。telnet时代就有的功能居然都
没实现。
string LongestMostTwoCharsSubString(string s) {
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
int uniqCharCounts = 0;
for (;;) {
for (;end < s.size(); ++end) {
if (++charCounts[s[end]] == 1) ++uniqCharCounts;
if (uniqCharCounts > 2) break;
}
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (uniqCharCounts > 2) {
if (--charCounts[s[start]] == 0) {
--uniqCharCounts;
break;
}
++start;
}
++start;
++end;
}
return s.substr(maxStart, maxLen);
}
【在 t*******i 的大作中提到】
: 不错，这个一改就可以适用于任何 N 个的情况
|
o****s
发帖数: 143 | 50 这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
挪动i指针往后吧。
比如说aabbcd， 应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
先移动i到b，这样res变成3了
【在 s******6 的大作中提到】
: 就是两个指针+一个计数的，假设是string是 acsii
: int longestSubstr(string s) {
: int count[256];
: memset(count, 0, sizeof(count));
: int cnt = 0;
: int i = 0;
: int res = 0;
: for(int j=0; j: count[s[j]] ++;
: if(count[s[j]] == 1) cnt ++;
|
|
|
m*****k
发帖数: 731 | 51 aabb时res就是4了
【在 o****s 的大作中提到】
: 这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
: 挪动i指针往后吧。
: 比如说aabbcd， 应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
: 先移动i到b，这样res变成3了
|
j**********3
发帖数: 3211 | |
f**********t
发帖数: 1001 | 53 // given a string ,return the longest substring that contains at most two
characters.
string twoChar(const string &s) {
if (s.empty()) {
return "";
}
char a, b;
int na = 0, nb = 0;
int left = 0;
int res = 0;
int pos = -1;
for (int right = 0; right < s.size(); ++right) {
if (0 < na && a == s[right]) {
++na;
} else if (0 < nb && b == s[right]) {
++nb;
} else if (na == 0) {
++na;
a = s[right];
} else if (nb == 0) {
++nb;
b = s[right];
} else {
if (res < na + nb) {
res = na + nb;
pos = left;
}
while (na > 0 && nb > 0) {
if (s[left] == a) {
--na;
} else {
--nb;
}
++left;
}
--right;
}
}
if (res < na + nb) {
res = na + nb;
pos = left;
}
return string(s.begin() + pos, s.begin() + pos + res);
} |
