陈东宇的博客

    1876. 长度为三且各字符不同的子字符串

    力扣原题（完整题面）

    题意

    统计字符串 s 中有多少个长度为 3、三个字符互不相同的连续子串。相同内容出现在不同位置时，要分别计数。

    样例 1

    输入：s = "xyzzaz"
输出：1

    解释：长度为 3 的子串依次是 "xyz"、"yzz"、"zza"、"zaz"，只有 "xyz" 的三个字符都不同。

    样例 2

    输入：s = "aababcabc"
输出：4

    解释：符合条件的子串是 "abc"、"bca"、"cab"、"abc"。两个 "abc" 位于不同位置，所以都要计数。

    解法一：直接检查每个窗口（我的做法）

    以 i 为窗口左端点，检查 s[i]、s[i+1] 和 s[i+2] 是否两两不同。三个比较都成立时，答案加一。窗口长度固定为 3，因此每轮判断的工作量是常数。

    class Solution {
public:
    int countGoodSubstrings(string s) {
        int ans = 0;
        int len = s.size();
        for (int i = 0; i < len - 2; ++i) {
            if (s[i] != s[i + 1] && s[i + 1] != s[i + 2] && s[i] != s[i + 2]) {
                ans++;
            }
        }
        return ans;
    }
};

    时间复杂度 O(n)，额外空间复杂度 O(1)，其中 n 是字符串长度。n < 3 时循环不会执行，答案自然为 0。

    解法二：字符频次滑动窗口

    也可以用长度为 3 的窗口维护每个字符的出现次数。右端加入一个字符；如果窗口超过 3 个字符，就移除左端字符。另用 distinct 记录窗口内不同字符的种数，当窗口长度为 3 且 distinct == 3 时，答案加一。

    class Solution {
public:
    int countGoodSubstrings(string s) {
        int count[26] = {};
        int distinct = 0;
        int ans = 0;

        for (int right = 0; right < static_cast<int>(s.size()); ++right) {
            int in = s[right] - 'a';
            if (count[in]++ == 0) {
                ++distinct;
            }

            if (right >= 3) {
                int out = s[right - 3] - 'a';
                if (--count[out] == 0) {
                    --distinct;
                }
            }

            if (right >= 2 && distinct == 3) {
                ++ans;
            }
        }
        return ans;
    }
};

    时间复杂度 O(n)，额外空间复杂度 O(1)。这道题的窗口只有三个字符，直接比较更简洁；频次数组写法适合推广到更长的固定窗口。