LeetCode 1358.包含所有三种字符的子字符串数目：滑动窗口(两种写法直接推荐方法二)

📅 2026/7/2 5:51:25 👁️ 次浏览

【LetMeFly】1358.包含所有三种字符的子字符串数目滑动窗口(两种写法直接推荐方法二)力扣题目链接https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/给你一个字符串s它只包含三种字符 a, b 和 c 。请你返回 ab 和 c 都至少出现过一次的子字符串数目。示例 1输入s abcabc输出10解释包含 ab 和 c 各至少一次的子字符串为abc, abca, abcab, abcabc, bca, bcab, bcabc, cab, cabc和abc(相同字符串算多次)。示例 2输入s aaacb输出3解释包含 ab 和 c 各至少一次的子字符串为aaacb, aacb和acb 。示例 3输入s abc输出1提示3 s.length 5 x 10^4s只包含字符 ab 和 c 。解题方法滑动窗口使用两个指针时刻满足指针之间的“窗口”是最短的同时包含abc的窗口。滑动方法一枚举窗口起点ll 到 r-1以及r的右边全合法——推荐方法二两个指针每次左指针l ll右移一位不断右移右指针r rr直到窗口[ l , r ) [l, r)[l,r)中含有三种字母。那么对于起点l ll其到r − 1 r-1r−1合法到话其到r rr、r 1 r1r1、⋯ \cdots⋯、n − 1 n-1n−1共计n − r 1 n-r1n−r1个都合法。滑动方法二枚举窗口终点rl-1以及l-1的左边到 r 全合法两个指针每次右指针r rr右移一位不断右移左指针l ll直到首次满足窗口[ l , r ] [l, r][l,r]中不含有三种字母。那么[ l − 1 , r ] [l-1, r][l−1,r]、[ l − 2 , r ] [l-2, r][l−2,r]、⋯ \cdots⋯、[ 0 , r ] [0, r][0,r]如果存在(共计l个)均合法。时空复杂度分析时间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))每个字母最多被遍历两次空间复杂度O ( 1 ) O(1)O(1)AC代码C——方法二/* * LastEditTime: 2026-07-01 15:38:27 */classSolution{public:intnumberOfSubstrings(string s){intans0;intcnt[3]{0};for(intl0,r0,ns.size();rn;r){cnt[s[r]-a];while(cnt[0]cnt[1]cnt[2]){cnt[s[l]-a]--;}ansl;}returnans;}};C——方法一/* * LastEditTime: 2026-07-01 15:34:43 */classSolution{public:intnumberOfSubstrings(string s){intans0;intcnt[3]{0};for(intl0,r0,ns.size();ln;l){while(rn!(cnt[0]cnt[1]cnt[2])){cnt[s[r]-a];}// printf(l %d, r %d, cnt {%d, %d, %d}, ans %d\n, l, r, cnt[0], cnt[1], cnt[2], n - r 1);ans(cnt[0]cnt[1]cnt[2])?n-r1:0;cnt[s[l]-a]--;}returnans;}};Python——方法二 LastEditTime: 2026-07-01 15:49:11 classSolution:defnumberOfSubstrings(self,s:str)-int:ans0cnt[0,0,0]lr0forrinrange(len(s)):cnt[ord(s[r])-ord(a)]1whilecnt[0]andcnt[1]andcnt[2]:cnt[ord(s[l])-ord(a)]-1l1anslreturnans同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源

相关新闻