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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

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

思路分析

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

核心思路：

使用双指针维护包含 a、b、c 的最短窗口。

当窗口已包含三种字符时，右端固定时可扩展的子串数为 n - right。

然后移动左指针继续收缩。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，固定 3 个字符计数。

class Solution {
    public int numberOfSubstrings(String s) {
        int[] count = new int[3];
        int left = 0;
        int res = 0;

        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'a']++;

            while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
                res += s.length() - right;
                count[s.charAt(left) - 'a']--;
                left++;
            }
        }

        return res;
    }
}

func numberOfSubstrings(s string) int {
	count := make([]int, 3)
	left := 0
	res := 0

	for right := 0; right < len(s); right++ {
		count[s[right]-'a']++

		for count[0] > 0 && count[1] > 0 && count[2] > 0 {
			res += len(s) - right
			count[s[left]-'a']--
			left++
		}
	}

	return res
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口
424. 替换后的最长重复字符	中等	滑动窗口
904. 水果成篮	中等	滑动窗口
992. K 个不同整数的子数组	困难	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/69432121