題目
Given a string S, find the length of the longest substring T that contains at most two distinct characters.
For example,
Given S = “eceba”,
T is “ece” which its length is 3.
解題之法
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int res = 0, left = 0;
unordered_map<char, int> m;
for (int i = 0; i < s.size(); ++i) {
++m[s[i]];
while (m.size() > 2) {
if (--m[s[left]] == 0) m.erase(s[left]);
++left;
}
res = max(res, i - left + 1);
}
return res;
}
};
分析
這道題給我們一個字符串，讓我們求最多有兩個不同字符的最長子串。那么我們首先想到的是用哈希表來做茎截，哈希表記錄每個字符的出現(xiàn)次數(shù)，然后如果哈希表中的映射數(shù)量超過兩個的時候祈争，我們需要刪掉一個映射，比如此時哈希表中e有2個角寸，c有1個菩混，此時把b也存入了哈希表，那么就有三對映射了扁藕，這時我們的left是0沮峡，先從e開始，映射值減1纹磺，此時e還有1個帖烘，不刪除，left自增1橄杨。這是哈希表里還有三對映射秘症，此時left是1，那么到c了式矫，映射值減1乡摹，此時e映射為0，將e從哈希表中刪除采转，left自增1聪廉，然后我們更新結果為i - left + 1，以此類推直至遍歷完整個字符串故慈。
