專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

據環球網昨日報道，胡某本是一名在校大學生，最近他利用所學技術非法入侵了學校某系統并獲取兩萬余條該校學生個人信息。

為尋求刺激、炫耀技術，胡某通過之前發現的某小程序存在的技術漏洞，利用AI編寫程序，把其中盜取的上千余名學生的手機號碼在該小程序上批量注冊賬戶，后將短信驗證碼篡改為淫穢內容發送至學生本人，對其進行短信騷擾。

這家伙也是沒底線，有這技術干啥不好，非要干一些非法的事，如果只是單純的發一些驗證碼估計也沒那么嚴重，非要把驗證碼改成淫穢內容發送到學生手機上，這簡直就是變態。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1358題：包含所有三種字符的子字符串數目，難度是中等。

給你一個字符串 s ，它只包含三種字符 a, b 和 c 。請你返回 a，b 和 c 都 至少 出現過一次的子字符串數目。

示例1：

輸入：s = "abcabc" 輸出：10 解釋：包含 a，b 和 c 各至少一次的子字符串為 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例2：

輸入：s = "aaacb" 輸出：3 解釋：包含 a，b 和 c 各至少一次的子字符串為 "aaacb", "aacb" 和 "acb" 。

• 3 <= s.length <= 5 x 10^4

• s 只包含字符 a，b 和 c 。

問題分析

這題說的是包含 3 種字符的子串數量，我們可以使用滑動窗口來解決。當窗口不包含 3 種字符的時候，要一直移動窗口的右邊界，直到窗口中包含 3 種字符為止。

當窗口包含 3 種字符的時候，說明這個窗口是滿足條件的子串，然后窗口中的字符和窗口右邊的字符構成的子串也是滿足條件的，這個不要遺漏，所以總共有 n-right 個，n 是字符串的長度，right 是窗口的右邊界，由于字符串的下標是從 0 開始的，所以這里不需要在加 1 。

然后移動窗口的左邊界，如果窗口還包含 3 種字符，說明窗口還是滿足條件的，然后繼續累加子串個數……

我們舉個例子，比如字符串“acabcc”，當窗口“acab”滿足條件的時候，“acab”和右邊的“cc”都可以構成滿足條件的子串，總共有 3 個。

縮小窗口為“cab”也是滿足條件的，它和右邊的“cc”也可以構成滿足條件的子串，又有 3 個。

繼續滑動窗口為“abc”也是滿足條件的，它和最后一個字符 “c” 也可以構成滿足條件的子串，又有 2 個。

所以總共有 8 個，分別是[acab,acabc,acabcc,cab,cabc,cabcc,abc,abcc]。

JAVA：

public int numberOfSubstrings(String s) {     int[] mp = newint[128];     int left = 0, right = 0, n = s.length();     int cnt = 0;// 新的字符個數     int ans = 0;// 返回的結果     while (right < n) {         if (mp[s.charAt(right)]++ == 0)// 遇到新的字符             cnt++;         while (cnt == 3) {             if (--mp[s.charAt(left++)] == 0)                 cnt--;// 移除一個新字符             ans += n - right;         }         right++;     }     return ans; }

C++：

public:     int numberOfSubstrings(string s) {         vector

  mp(128, 0);         int left = 0, right = 0, n = s.length();         int cnt = 0;// 新的字符個數         int ans = 0;// 返回的結果         while (right < n) {             if (mp[s[right]]++ == 0)// 遇到新的字符                 cnt++;             while (cnt == 3) {                 if (--mp[s[left++]] == 0)                     cnt--;// 移除一個新字符                 ans += n - right;             }             right++;         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。