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.
这个题很显然使用双指针进行遍历的，begin与end之间的窗口代表符合要求的字符子串。
解法一：
inWindow数组保存窗口中的两个不同字符。（若找不到两个不同的字符，直接返回字符串长度）
map<char, int>保存inWindow中两个字符在窗口中的出现次数。
判断新字符的标准为不等于inWindow数组的任一字符，那么就需要收缩begin，直到inWindow腾出空间给新字符。
class Solution { public: int lengthOfLongestSubstringTwoDistinct(string s) { if(s == "") return 0; else if(s.size() <= 2) return s.size(); //slip window [begin, end] //initial the window with two different chars int size = s.size(); int begin = 0; int end = 1; 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[2] = {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]] = 1; int longest = end-begin+1; end ++; while(end < size) { m[s[end]] ++; if(s[end] == inWindow[0] || s[end] == inWindow[1]) //in window, extend end longest = max(longest, end-begin+1); else {//not in window, shrink begin //remove a char from window while(m[inWindow[0]] != 0 && m[inWindow[1]] != 0) { m[s[begin]] --; begin ++; } //to here, either m[inWindow[0]] == 0 or m[inWindow[1]] == 0 if(m[inWindow[0]] == 0) inWindow[0] = s[end]; else inWindow[1] = 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() <= 2) return s.size(); int size = s.size(); int record[128] = {0}; //record the appearance times of each char. Note ‘z‘ is 122, 128 is enough. int begin = 0; int end = 0; int count = 0; //distinct count int longest = 0; while(end < size) { record[s[end]] ++; if(record[s[end]] == 1) //new char count ++; while(count > 2) {//shrink record[s[begin]] --; if(record[s[begin]] == 0) count --; //remove one char begin ++; } longest = max(longest, end-begin+1); end ++; } return longest; } };
我编写的测试用例如下，上述两个解法代码全部通过。
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"
【LeetCode】Longest Substring with At Most Two Distinct Characters (2 solutions)
原文：http://www.cnblogs.com/ganganloveu/p/4190069.html