Easy

题目描述

如果一个字符串没有重复字符，则该字符串是好的。

给定一个字符串 s，返回 s 中长度为三的好子串的数量。

注意，如果同一个子串出现多次，每次出现都应该计数。

子串是字符串中字符的连续序列。

示例 1：

输入：s = "xyzzaz"
输出：1
解释：有 4 个长度为 3 的子串："xyz", "yzz", "zza", 和 "zaz"。
其中只有 "xyz" 是长度为 3 的好子串。

示例 2：

输入：s = "aababcabc"
输出：4
解释：有 7 个长度为 3 的子串："aab", "aba", "bab", "abc", "bca", "cab", 和 "abc"。
好子串是 "abc", "bca", "cab", 和 "abc"。

提示：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母

提示：

  • 尝试使用集合来找出子串中不同字符的数量。

解题思路

这道题要求统计长度为 3 的不包含重复字符的子串数量。

思路分析：

由于子串长度固定为 3，我们可以使用滑动窗口的方法。对于每个长度为 3 的窗口，检查三个字符是否都不相同。

具体实现有两种常见方法：

  1. 暴力遍历法：遍历所有可能的长度为 3 的子串，对每个子串检查三个字符是否互不相同。时间复杂度 O(n)，空间复杂度 O(1)。

  2. 集合判重法：对于每个长度为 3 的子串，使用集合（Set）来判断字符数量是否等于 3。如果集合大小为 3，说明三个字符都不相同。

推荐解法：暴力遍历法

由于长度固定为 3，我们可以直接比较三个字符是否两两不同。这比使用集合更高效，因为避免了创建额外数据结构的开销。

对于每个起始位置 i（i 从 0 到 s.length-3），检查 s[i]、s[i+1]、s[i+2] 是否两两不同。如果满足条件，计数器加 1。

这种方法简单直观，时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

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

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        if len(s) < 3:
            return 0
        
        count = 0
        for i in range(len(s) - 2):
            if s[i] != s[i+1] and s[i+1] != s[i+2] and s[i] != s[i+2]:
                count += 1
        return count

public class Solution {
    public int CountGoodSubstrings(string s) {
        if (s.Length < 3) return 0;
        
        int count = 0;
        for (int i = 0; i <= s.Length - 3; i++) {
            if (s[i] != s[i+1] && s[i+1] != s[i+2] && s[i] != s[i+2]) {
                count++;
            }
        }
        return count;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var countGoodSubstrings = function(s) {
    if (s.length < 3) return 0;
    
    let count = 0;
    for (let i = 0; i <= s.length - 3; i++) {
        if (s[i] !== s[i+1] && s[i+1] !== s[i+2] && s[i] !== s[i+2]) {
            count++;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 为字符串 s 的长度。我们需要遍历所有可能的长度为 3 的子串，每次检查操作为常数时间，因此总时间复杂度为 O(n)。算法只使用了常数个额外变量，空间复杂度为 O(1)。