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

🟢   🔖  哈希表 字符串 计数 滑动窗口  🔗 力扣 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;
};