1358. 包含所有三种字符的子字符串数目

题目链接：https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/

代码

/**
 * 1358. 包含所有三种字符的子字符串数目
 * https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/
 */

function numberOfSubstrings1(s: string): number {
    let left = 0;
    let res = 0;
    const map = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
        map.set(s[i], (map.get(s[i]) || 0) + 1);
        // map.size === 3说明当前窗口[left, i]已经包含abc
        while (map.size === 3) {
            const c = s[left];
            if (map.get(c) === 1) {
                map.delete(c);
            } else {
                map.set(c, map.get(c)! - 1);
            }
            // left推到了刚好不再满足包含 3 个字符的位置
            left++;
        }
        // [0, i][1, i]...[left - 1, i]一共有left个合法子串
        res += left;
    }
    return res;
}

思路

滑动窗口 + 哈希表统计字符数量：

使用哈希表 map 记录窗口内每种字符（a、b、c）的数量
对于每个右端点 i：
- 将 s[i] 加入窗口，更新计数
- 当窗口包含所有三种字符（map.size === 3）时，收缩左边界 left，直到窗口不再包含所有三种字符
- 此时 left 指向第一个不再满足条件的位置，以 i 为右端点的所有有效子字符串数量为 left（即 [0, i], [1, i], ..., [left-1, i] 共 left 个）
累加所有右端点对应的子字符串数量

时间复杂度 $O (n)$ ，每个字符最多被访问两次（加入和移除窗口各一次）
空间复杂度 $O (1)$ ，哈希表最多存储 3 种字符

1358. 包含所有三种字符的子字符串数目 ​

代码 ​

思路 ​

1358. 包含所有三种字符的子字符串数目

代码

思路