【LeetCode】Longest Substring with At Most Two Distinct Characters (2 solutions)

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.

可与Longest Substring Without Repeating Characters对照看。

这个题很显然使用双指针进行遍历的，begin与end之间的窗口代表符合要求的字符子串。

解法一：

inWindow数组保存窗口中的两个不同字符。（若找不到两个不同的字符，直接返回字符串长度）

map<char, int>保存inWindow中两个字符在窗口中的出现次数。

判断新字符的标准为不等于inWindow数组的任一字符，那么就需要收缩begin，直到inWindow腾出空间给新字符。

class Solution

{

public:

    int lengthOfLongestSubstringTwoDistinct(string s)

    {

        if(s == "")

            return ;

        else if(s.size() <= )

            return s.size();

        //slip window [begin, end]

        //initial the window with two different chars

        int size = s.size();

        int begin = ;

        int end = ;

        while(end < size && s[end] == s[begin])

            end ++;

        //to here, end == size or s[end] != s[begin]

        if(end == size)

            return size;    //all chars are the same

        char inWindow[] = {s[begin], s[end]};

        map<char, int> m;    //char->count map

        m[s[begin]] = end-begin;    //[begin,end) are all s[begin]

        m[s[end]] = ;

        int longest = end-begin+;

        end ++;

        while(end < size)

        {

            m[s[end]] ++;

            if(s[end] == inWindow[] || s[end] == inWindow[])

            //in window, extend end

                longest = max(longest, end-begin+);

            else

            {//not in window, shrink begin

                //remove a char from window

                while(m[inWindow[]] !=  && m[inWindow[]] != )

                {

                    m[s[begin]] --;

                    begin ++;

                }

                //to here, either m[inWindow[0]] == 0 or m[inWindow[1]] == 0

                if(m[inWindow[]] == )

                    inWindow[] = s[end];

                else

                    inWindow[] = s[end];

            }

            end ++;

        }

        return longest;

    }

};

解法二：

由于A~Z,a~z的ASCII码不超过122，因此开辟128的数组record进行窗口中每个字符的计数。

再设置计数位count，记录当前窗口中有多少个不同的字符。

判断新字符的标准为record值为1（加入新字符之后）。

如果count>2，那么就需要收缩begin，直到s[begin]对应的计数为0，代表少了一类字符，count--

class Solution

{

public:

    int lengthOfLongestSubstringTwoDistinct(string s)

    {

        if(s.size() <= )

            return s.size();

        int size = s.size();

        int record[] = {};    //record the appearance times of each char. Note 'z' is 122, 128 is enough.

        int begin = ;

        int end = ;

        int count = ;    //distinct count

        int longest = ;

        while(end < size)

        {

            record[s[end]] ++;

            if(record[s[end]] == )

            //new char

                count ++;

            while(count > )

            {//shrink

                record[s[begin]] --;

                if(record[s[begin]] == )

                    count --;

                //remove one char

                begin ++;

            }

            longest = max(longest, end-begin+);

            end ++;

        }

        return longest;

    }

};

我编写的测试用例如下，上述两个解法代码全部通过。

int main()

{

    string str1 = "";                //expect: 0 ""

    string str2 = "a";                //expect: 1 "a"

    string str3 = "aa";                //expect: 2 "aa"

    string str4 = "aba";            //expect: 3 "aba"

    string str5 = "abcd";            //expect: 2 "ab"

    string str6 = "abcdedcba";        //expect: 3 "ded"

    string str7 = "abbcdededcba";    //expect: 5 "deded"

    string str8 = "eceba";            //expect: 3 "ece"

    string str9 = "abaece";            //expect: 3 "aba"

    string str10 = "ababcd";        //expect: 4 "abab"

    string str11 = "cababcd";        //expect: 4 "abab"

    string str12 = "abcdefgabcdefg";//expect: 2 "ab"

    string str13 = "ababababababab";//expect: 14 "ababababababab"

    Solution s;

    cout << s.lengthOfLongestSubstringTwoDistinct(str1) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str2) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str3) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str4) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str5) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str6) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str7) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str8) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str9) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str10) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str11) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str12) << endl;

    cout << s.lengthOfLongestSubstringTwoDistinct(str13) << endl;

}

巴特西

【LeetCode】Longest Substring with At Most Two Distinct Characters (2 solutions)

最新文章

热门文章