[LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有兩個(gè)不同字符的最長(zhǎng)子串

Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: tis "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.

這道題給我們一個(gè)字符串，讓求最多有兩個(gè)不同字符的最長(zhǎng)子串。那么首先想到的是用 HashMap 來做，HashMap 記錄每個(gè)字符的出現(xiàn)次數(shù)，然后如果 HashMap 中的映射數(shù)量超過兩個(gè)的時(shí)候，這里需要?jiǎng)h掉一個(gè)映射，比如此時(shí) HashMap 中e有2個(gè)，c有1個(gè)，此時(shí)把b也存入了 HashMap，那么就有三對(duì)映射了，這時(shí) left 是0，先從e開始，映射值減1，此時(shí)e還有1個(gè)，不刪除，left 自增1。這時(shí) HashMap 里還有三對(duì)映射，此時(shí) left 是1，那么到c了，映射值減1，此時(shí)e映射為0，將e從 HashMap 中刪除，left 自增1，然后更新結(jié)果為 i - left + 1，以此類推直至遍歷完整個(gè)字符串，參見代碼如下：

解法一：

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;
    }
};

我們除了用 HashMap 來映射字符出現(xiàn)的個(gè)數(shù)，還可以映射每個(gè)字符最新的坐標(biāo)，比如題目中的例子 "eceba"，遇到第一個(gè)e，映射其坐標(biāo)0，遇到c，映射其坐標(biāo)1，遇到第二個(gè)e時(shí)，映射其坐標(biāo)2，當(dāng)遇到b時(shí)，映射其坐標(biāo)3，每次都判斷當(dāng)前 HashMap 中的映射數(shù)，如果大于2的時(shí)候，那么需要?jiǎng)h掉一個(gè)映射，還是從 left=0 時(shí)開始向右找，看每個(gè)字符在 HashMap 中的映射值是否等于當(dāng)前坐標(biāo) left，比如第一個(gè)e，HashMap 此時(shí)映射值為2，不等于 left 的0，那么 left 自增1，遇到c的時(shí)候，HashMap 中c的映射值是1，和此時(shí)的 left 相同，那么我們把c刪掉，left 自增1，再更新結(jié)果，以此類推直至遍歷完整個(gè)字符串，參見代碼如下：

解法二：

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]] = i;
            while (m.size() > 2) {
                if (m[s[left]] == left) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

后來又在網(wǎng)上看到了一種解法，這種解法是維護(hù)一個(gè) sliding window，指針 left 指向起始位置，right 指向 window 的最后一個(gè)位置，用于定位 left 的下一個(gè)跳轉(zhuǎn)位置，思路如下：

1. 若當(dāng)前字符和前一個(gè)字符相同，繼續(xù)循環(huán)。

2. 若不同，看當(dāng)前字符和 right 指的字符是否相同

    (1) 若相同，left 不變，右邊跳到 i - 1

    (2) 若不同，更新結(jié)果，left 變?yōu)?right+1，right 變?yōu)?i - 1

最后需要注意在循環(huán)結(jié)束后，還要比較結(jié)果 res 和 s.size() - left 的大小，返回大的，這是由于如果字符串是 "ecebaaa"，那么當(dāng) left=3 時(shí)，i=5,6 的時(shí)候，都是繼續(xù)循環(huán)，當(dāng)i加到7時(shí)，跳出了循環(huán)，而此時(shí)正確答案應(yīng)為 "baaa" 這4個(gè)字符，而我們的結(jié)果 res 只更新到了 "ece" 這3個(gè)字符，所以最后要判斷 s.size() - left 和結(jié)果 res 的大小。

另外需要說明的是這種解法僅適用于于不同字符數(shù)為2個(gè)的情況，如果為k個(gè)的話，還是需要用上面兩種解法。

解法三：

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int left = 0, right = -1, res = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i - 1]) continue;
            if (right >= 0 && s[right] != s[i]) {
                res = max(res, i - left);
                left = right + 1;
            }
            right = i - 1;
        }
        return max(s.size() - left, res);
    }
};

還有一種不使用 HashMap 的解法，是在做 Fruit Into Baskets 這道題的時(shí)候在論壇上看到的，其實(shí)這兩道題除了背景設(shè)定之外沒有任何的區(qū)別，代碼基本上都可以拷來直接用的。這里使用若干的變量，其中 cur 為當(dāng)前最長(zhǎng)子串的長(zhǎng)度，first 和 second 為當(dāng)前候選子串中的兩個(gè)不同的字符，cntLast 為 second 字符的連續(xù)長(zhǎng)度。遍歷所有字符，假如遇到的字符是 first 和 second 中的任意一個(gè)，那么 cur 可以自增1，否則 cntLast 自增1，因?yàn)槿羰切伦址脑挘J(rèn)已經(jīng)將 first 字符淘汰了，此時(shí)候選字符串由 second 字符和這個(gè)新字符構(gòu)成，所以當(dāng)前長(zhǎng)度是 cntLast+1。然后再來更新 cntLast，假如當(dāng)前字符等于 second 的話，cntLast 自增1，否則均重置為1，因?yàn)?cntLast 統(tǒng)計(jì)的就是 second 字符的連續(xù)長(zhǎng)度。然后再來判斷若當(dāng)前字符不等于 second，則此時(shí) first 賦值為 second， second 賦值為新字符。最后不要忘了用 cur 來更新結(jié)果 res，參見代碼如下：

解法四：

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int res = 0, cur = 0, cntLast = 0;
        char first, second;
        for (char c : s) {
            cur = (c == first || c == second) ? cur + 1 : cntLast + 1;
            cntLast = (c == second) ? cntLast + 1 : 1;
            if (c != second) {
                first = second; second = c;
            }
            res = max(res, cur);
        }
        return res;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/159

類似題目：

Fruit Into Baskets

Longest Substring Without Repeating Characters

Sliding Window Maximum

Longest Substring with At Most K Distinct Characters

Subarrays with K Different Integers

參考資料：

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49759/Share-my-c%2B%2B-solution

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49687/Clean-11-lines-AC-answer-O(1)-space-O(n)-time.

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49682/Simple-O(n)-java-solution-easily-extend-to-k-characters

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49708/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem.

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(159.最多有兩個(gè)不同字符的最長(zhǎng)子串)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)最多有兩個(gè)不同字符的最長(zhǎng)子串內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論