[LeetCode] 1358. Number of Substrings Containing All Three Characters 包含所有三種字符的子字符串數目

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

3 <= s.length <= 5 x 10^4
s only consists of a, b or *c *characters.

這道題給了一個只有 a，b，c 三個字母構成的字符串s，現在讓找出三個字母均至少出現一次的子串的個數。一般玩字符串的題目無外乎就是滑動窗口 Sliding Window 和動態規劃 Dynamic Programming 用的比較多。這道題不太適合用 DP，狀態轉移方程不太好找。來看看能否用滑動窗口來做吧，如果題目讓求的是三個字母都只出現一次的話，想必大家應該都沒啥問題，這里的至少出現一次也算是個難點了，就拿例子1來分析，當滑動窗口套住第一個 abc 的時候，此時除了其本身是符合要求的，其后面的每個字母都可以跟窗口里的字母組成符合要求的子串，組成 abca, abcab, abcabc，這樣統計的個數世紀上就是 n-i，n是原字符串s的總長度，i是當前滑動窗口的右邊界，整個步驟如下所示：

[a b c] a b c
abc, abca, abcab, ababc

a [b c a] b c
bca, bcab, bcabc

a b [c a b] c
cab, cabc

a b c [a b c]
abc

通過上面這種計數方法，我們就可以不重復的統計出所有滿足情況的子串。當然這種統計方法也不是唯一的，比如 lee215 大神用的就是另一種統計方法，其主要是統計左邊界前面的字母個數，也是可以的，參見代碼如下：

解法一：

class Solution {
public:
    int numberOfSubstrings(string s) {
        int res = 0, n = s.size(), left = 0;
        vector<int> cnt(3);
        for (int i = 0; i < n; ++i) {
            ++cnt[s[i] - 'a'];
            while (cnt[0] && cnt[1] && cnt[2]) {
                res += n - i;
                --cnt[s[left++] - 'a'];
            }
        }
        return res;
    }
};

再來看一種更加簡潔的解法，這里記錄 a，b，c 最后出現的位置，初始化為-1，然后每次取其中最小的數字，再加上1就是當前范圍內符合要求的子串的個數。當最小值為初始的 -1 時，說明某個字母沒有出現過，則加上0不影響結果，而當最小的大于等于0了，說明每個字母都出現過了，而最小的那個值就相當于滑動窗口的左邊界，其實還是統計左邊界前面的字母個數，參見計數過程如下：

a b c a b c

i = 0, [0, -1, -1], min = -1
i = 1, [0, 1, -1], min = -1
i = 2, [0, 1, 2], min = 0 -> abc
i = 3, [3, 1, 2], min = 1 -> abca, bca
i = 4, [3, 4, 2], min = 2 -> abcab, bcab, cab
i = 5, [3, 4, 5], min = 3 -> abcabc, bcabc, cabc, abc

解法二：

class Solution {
public:
    int numberOfSubstrings(string s) {
        int res = 0, n = s.size();
        vector<int> last(3, -1);
        for (int i = 0; i < n; ++i) {
            last[s[i] - 'a'] = i;
            res += 1 + min({last[0], last[1], last[2]});
        }
        return res;
    }
};

Github 同步地址:

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

類似題目：

Vowels of All Substrings

參考資料：

https://leetcode.com/problems/number-of-substrings-containing-all-three-characters

https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/solutions/516977/java-c-python-easy-and-concise/

https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/solutions/3459766/explained-w-images-made-easy-c/

LeetCode All in One 題目講解匯總(持續更新中...)