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

题目描述

如果一个字符串不含有任何重复字符，我们称这个字符串为 好 字符串。 给你一个字符串 s ，请你返回 s 中长度为 3 的 好子字符串 的数量。 注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。 子字符串 是一个字符串中连续的字符序列。 示例 1： 输入：s = "xyzzaz" 输出：1 解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。 唯一的长度为 3 的好子字符串是 "xyz" 。 示例 2： 输入：s = "aababcabc" 输出：4 解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。 好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。 提示： 1 <= s.length <= 100 s 只包含小写英文字母。

题目解析

好的，没问题！我们一起来把这道题讲明白。

题目在说什么

简单来说，就是给你一个字符串，比如 "xyzzaz"。我们要从里面找出所有长度为3的“好”子字符串。

• 子字符串：就是字符串里连续的一段。比如 "xyz"、"yzz"、"zza"、"zaz" 都是长度为3的子字符串。
• 好：指的是这个长度为3的子字符串里，三个字符互不相同，没有重复的。

题目问我们，这样的“好”子字符串一共有多少个。注意，同一个“好”子字符串如果出现多次，比如 "abc" 出现了两次，那就要算两次。

思路是怎么来的

想象一下，你有一串很长的珠子，每个珠子上有一个字母。你想检查所有连续的、长度为3的一小段珠子，看看它们是不是三个字母都不一样。

最直接、最笨的办法是什么？就是从第一个珠子开始，每次取连续的三颗，检查一下，然后往后挪动一颗珠子，再取连续的三颗，再检查……直到最后。

这个思路非常自然，就像我们用手在一串珠子上滑动着看一样。我们把这种办法叫做 “滑动窗口”。

• 窗口：就是每次我们看的那个长度为3的小段。
• 滑动：就是每次检查完，我们把窗口整体往后移动一个位置。

那么，怎么检查一个窗口里的三个字符是否互不相同呢？也很简单，就是两两比较一下： 1. 第一个字符和第二个字符相等吗？ 2. 第一个字符和第三个字符相等吗？ 3. 第二个字符和第三个字符相等吗？

如果这三个问题答案都是“不相等”，那么这三个字符就互不相同，就是一个“好”子字符串。

代码逐步拆解

我们来看一下用代码怎么实现这个思路。这里我用一种非常直观的写法，方便你理解。

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        # 1. 准备一个计数器，用来记录“好”子字符串的数量
        good_count = 0

        # 2. 开始滑动窗口
        # 窗口的起始位置是 i，结束位置是 i+2。
        # 窗口从索引 0 开始，一直滑动到 s 的倒数第三个字符（索引 len(s)-3）。
        # 因为窗口长度为3，最后一个窗口的起始位置是 len(s)-3。
        for i in range(len(s) - 2):
            # 3. 取出当前窗口的三个字符
            first = s[i]
            second = s[i+1]
            third = s[i+2]

            # 4. 检查这三个字符是否互不相同
            # 如果 first 不等于 second，且 first 不等于 third，且 second 不等于 third
            if first != second and first != third and second != third:
                # 5. 如果满足条件，就说明找到了一个“好”子字符串，计数器加1
                good_count += 1

        # 6. 循环结束后，返回计数器的值
        return good_count

逐步拆解：

1. `good_count = 0`：就像我们准备了一个空白的本子，每找到一个“好”的，就记一笔。一开始肯定是0。

2. `for i in range(len(s) - 2):`：这是整个代码的核心，就是“滑动”。

• len(s) 是字符串的长度。比如 s = "xyzzaz"，长度是6。
• range(len(s) - 2) 就是 range(4)，它会生成 0, 1, 2, 3 这四个数字。
• i 代表窗口的起始位置。
• 当 i=0 时，窗口是 s[0], s[1], s[2]，也就是 "xyz"。
• 当 i=1 时，窗口是 s[1], s[2], s[3]，也就是 "yzz"。
• 当 i=2 时，窗口是 s[2], s[3], s[4]，也就是 "zza"。
• 当 i=3 时，窗口是 s[3], s[4], s[5]，也就是 "zaz"。
• 为什么是 len(s)-2 而不是 len(s)？因为窗口长度为3，最后一个窗口的起始位置必须是倒数第三个字符。如果 i 取到 len(s)-1，那窗口就会超出字符串范围了。

3. `first = s[i]`，`second = s[i+1]`，`third = s[i+2]`：这一步就是把当前窗口里的三个字符分别取出来，起个名字，方便后面比较。就像你从珠串上取下三颗珠子放在手里看。