[Locked] Longest Substring with At Most Two Distinct Characters

Longest Substring with At Most Two Distinct Characters

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.

分析：

　　最多包含两个不同字母的子串，至少要遍历一遍，复杂度为O(n)，而要实现O(n)复杂度，用移动窗口思想即可。

代码：

int lentwoc(string s) {

    if(s.empty())

        return ;

    char a = s[], b = '\0';

    //alast为a字母最后出现的位置，blast为b字母最后出现的位置，lastpos为新两元序列的开端位置，maxl为全局最长序列长度

    int alast = , blast = -, lastpos = , maxl = ;

    for(int i = ; i < s.length(); i++) {

        //开启新两元序列

        if(s[i] != a && s[i] != b) {

            //记录前一个两元序列长度

            maxl = max(i - lastpos, maxl);

            if(alast < blast) {

                alast = i;

                a = s[i];

                lastpos = blast;

            }

            else {

                blast = i;

                b = s[i];

                lastpos = alast;

            }

        }

        else

            s[i] == a ? alast = i : blast = i;

    }

    return maxl;

}