【最新的谷歌java面试题】找出字符串中只包含两种字符的最长子串

给出一个字符串,找出只包含2种字符的最长子串。如aabbcbbbadef,结果是bbcbbb。

string longestSubStrWith2Chars(const string &s)
{
int len = s.length();

// 空串返回空串
if(len == 0)
return “”;

char ch1, ch2;
int ch1LastPos, ch2LastPos;

ch1 = s[0];
int i = 0;
while(i < len && s[i] == ch1)
++i;
ch1LastPos = i-1;

// 只有一个字符返回空串
if(i == len)
return “”;

ch2 = s[i];
while(i < len && s[i] == ch2)
++i;
ch2LastPos = i-1;

int lenMax = i;
int startPosMax = 0;
int startPosCur = 0;
while(i < len)
{
if(s[i] == ch1)
ch1LastPos = i;
else if(s[i] == ch2)
ch2LastPos = i;
else
{
if(ch1LastPos < ch2LastPos)
{
ch1 = s[i];
startPosCur = ch1LastPos+1;
ch1LastPos = i;
}
else
{
ch2 = s[i];
startPosCur = ch2LastPos+1;
ch2LastPos = i;
}
}

if(i-startPosCur+1 > lenMax)
{
lenMax = i-startPosCur+1;
startPosMax = startPosCur;
}
++i;
}

return s.substr(startPosMax, lenMax);
}

标签