1876.md

title	description	keywords
1876. 长度为三且各字符不同的子字符串	LeetCode 1876. 长度为三且各字符不同的子字符串题解，Substrings of Size Three with Distinct Characters，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1876. 长度为三且各字符不同的子字符串 长度为三且各字符不同的子字符串 Substrings of Size Three with Distinct Characters 解题思路 哈希表 字符串 计数 滑动窗口

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

🟢 Easy  🔖  哈希表 字符串 计数 滑动窗口  🔗 力扣 LeetCode

题目

A string is good if there are no repeated characters.

Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "xyzzaz"

Output: 1

Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".

The only good substring of length 3 is "xyz".

Example 2:

Input: s = "aababcabc"

Output: 4

Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".

The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

• 1 <= s.length <= 100
• s​​​​​​ consists of lowercase English letters.

题目大意

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

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

解题思路

1. 初始化三个指针：

   • 可以通过三个变量 a, b, 和 c 来表示当前滑动窗口内的 3 个字符。
   • 初始时，a, b, c 是第一个窗口（s[0], s[1], s[2]）的字符

2. 滑动窗口：

   • 从 i = 3 开始遍历，逐个更新 a, b, c。对于每个更新的窗口，
   • 每次滑动时，判断窗口中的字符是否全部不同（即 a != b && b != c && a != c）
   • 如果是，则计数 count 加 1。

3. 最后一个窗口的处理：

   • 遍历结束后，还需要处理最后一个窗口的判断，因为最后的窗口没有通过循环被检查。

4. 返回结果：

   • 最终返回 count，即符合条件的子串数量。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，只需遍历字符串一次，并进行常数时间的判断操作。
• 空间复杂度：O(1)，只用了常数级别的额外空间来存储字符。

代码

/**
 * @param {string} s
 * @return {number}
 */
var countGoodSubstrings = function (s) {
	let count = 0;
	// 初始化前三个字符
	let a = s[0],
		b = s[1],
		c = s[2];

	// 从第4个字符开始遍历
	for (let i = 3; i < s.length; i++) {
		// 如果当前窗口内的3个字符都不相同
		if (a != b && b != c && a != c) {
			count++;
		}
		// 更新窗口
		a = b;
		b = c;
		c = s[i];
	}

	// 最后一个窗口的判断
	if (a != b && b != c && a != c) {
		count++;
	}

	return count;
};