What is a 'good' substring in Substrings of Size Three with Distinct Characters?

A 'good' substring has exactly three characters with no repetitions, meaning all characters are unique.

Can I use nested loops instead of a sliding window?

Yes, but a sliding window is more efficient for checking consecutive substrings of size three.

Does the order of characters matter?

Yes, the substring is contiguous in the original string, so the order matters for both uniqueness and counting.

How do I handle multiple occurrences of the same substring?

Each occurrence is counted separately; do not merge or remove duplicates when incrementing the result.

Is a set or hash table necessary for this sliding window problem?

Using a set or hash table simplifies checking for distinct characters and follows the sliding window pattern efficiently.

#1876

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

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

如果一个字符串不含有任何重复字符，我们称这个字符串为好字符串。给你一个字符串 s ，请你返回 s 中长度为 3 的好子字符串的数量。注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。子字符串是一个字符串中连续的字符序列。示例 1：输入： s = "xyzzaz" 输…

哈希表字符串滑动窗口计数

题目描述

如果一个字符串不含有任何重复字符，我们称这个字符串为好字符串。

给你一个字符串 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 只包含小写英文字母。

lightbulb

解题思路

方法一：滑动窗口

我们可以维护一个滑动窗口，使得窗口内的字符不重复。初始时，我们用一个长度为 $26$ 的二进制整数 $\textit{mask}$ 表示窗口内的字符，其中第 $i$ 位为 $1$ 表示字符 $i$ 在窗口内出现过，否则表示字符 $i$ 在窗口内没有出现过。

然后，我们遍历字符串 $s$ ，对于每一个位置 $r$ ，如果 $\textit{s}[r]$ 在窗口内出现过，我们需要将窗口的左边界 $l$ 右移，直到窗口内不再有重复的字符。在这之后，我们将 $\textit{s}[r]$ 加入窗口内，此时如果窗口的长度大于等于 $3$ ，那么我们就找到了一个以 $\textit{s}[r]$ 结尾的长度为 $3$ 的好子字符串。

遍历结束后，我们就找到了所有的好子字符串的数量。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

该解法可以拓展到长度为 $k$ 的好子字符串的数量。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        ans = mask = l = 0
        for r, x in enumerate(map(lambda c: ord(c) - 97, s)):
            while mask >> x & 1:
                y = ord(s[l]) - 97
                mask ^= 1 << y
                l += 1
            mask |= 1 << x
            ans += int(r - l + 1 >= 3)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each character is visited once in the sliding window. Space complexity is O(1) because the set or hash table only tracks at most three characters at a time.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Emphasis on sliding window to check all substrings of fixed size.
question_mark
Looking for use of a set or hash table to quickly detect distinct characters.
question_mark
Expect attention to counting every occurrence of a good substring without missing duplicates.

warning

常见陷阱

外企场景

error
Counting only unique substrings instead of all occurrences.
error
Forgetting to reset or update the set/hash table correctly when sliding the window.
error
Comparing characters incorrectly and miscounting substrings with repeated letters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count substrings of length k with distinct characters for any k > 1.
arrow_right_alt
Return all good substrings instead of just counting them.
arrow_right_alt
Check for substrings of size three that have exactly two distinct characters.

help

常见问题

外企场景

继续练习

#1897 重新分配字符使所有字符串都相等 #1941 检查是否所有字符出现次数相同 #1790 仅执行一次字符串交换能否使两个字符串相等