Medium

题目描述

给你一个仅由字符 a、b 和 c 组成的字符串 s 。

返回至少包含这些字符 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 = "abc"
输出：1

提示：

  • 3 <= s.length <= 5 x 10^4
  • s 仅由字符 ‘a’、‘b’ 和 ‘c’ 组成。

解题思路

这道题要统计包含至少一个 a、b、c 的子字符串数量，可以使用滑动窗口或枚举右端点的方法。

解法一：滑动窗口（推荐）

使用滑动窗口维护一个包含所有三种字符的最小窗口。对于每个右端点，找到最左边能形成合法子串的左端点，那么从字符串开始到这个左端点的所有位置都可以作为左端点。

具体做法：

  1. 用哈希表记录当前窗口内各字符的出现次数
  2. 右指针不断扩展，当窗口包含所有三种字符时，尝试收缩左指针
  3. 对于每个右端点，所有从0到left的位置都可以作为左端点，贡献 left+1 个子串

解法二：记录最近位置

对于每个位置i作为右端点，找到在i及之前最晚出现的a、b、c的位置，取最小值作为左边界。

时间复杂度都是O(n)，空间复杂度O(1)。第一种解法更直观易懂。

代码实现

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.length();
        int count[3] = {0, 0, 0};  // 记录a,b,c的出现次数
        int left = 0, result = 0;
        
        for (int right = 0; right < n; right++) {
            count[s[right] - 'a']++;
            
            // 当窗口包含所有三种字符时，收缩左指针
            while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
                result += n - right;  // 所有以right为右端点的合法子串
                count[s[left] - 'a']--;
                left++;
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        count = [0, 0, 0]  # 记录a,b,c的出现次数
        left = 0
        result = 0
        
        for right in range(n):
            count[ord(s[right]) - ord('a')] += 1
            
            # 当窗口包含所有三种字符时，收缩左指针
            while count[0] > 0 and count[1] > 0 and count[2] > 0:
                result += n - right  # 所有以right为右端点的合法子串
                count[ord(s[left]) - ord('a')] -= 1
                left += 1
        
        return result

public class Solution {
    public int NumberOfSubstrings(string s) {
        int n = s.Length;
        int[] count = new int[3];  // 记录a,b,c的出现次数
        int left = 0, result = 0;
        
        for (int right = 0; right < n; right++) {
            count[s[right] - 'a']++;
            
            // 当窗口包含所有三种字符时，收缩左指针
            while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
                result += n - right;  // 所有以right为右端点的合法子串
                count[s[left] - 'a']--;
                left++;
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function(s) {
    const n = s.length;
    const count = [0, 0, 0];  // 记录a,b,c的出现次数
    let left = 0, result = 0;
    
    for (let right = 0; right < n; right++) {
        count[s.charCodeAt(right) - 97]++;
        
        // 当窗口包含所有三种字符时，收缩左指针
        while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
            result += n - right;  // 所有以right为右端点的合法子串
            count[s.charCodeAt(left) - 97]--;
            left++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度滑动窗口解法
时间复杂度O(n)
空间复杂度O(1)

相关题目