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

探寻字符串里长度为 3 的无重复字符子字符串

题目描述

给定一个字符串 s，需要找出其中所有长度为 3 的 “好子字符串”，也就是不含有任何重复字符的连续子字符串，并统计其数量。需要注意的是，即便相同的好子字符串多次出现，每次都要计入结果。

解题思路剖析

核心思路

• 直接遍历法：对字符串进行遍历，从每个位置开始截取长度为 3 的子字符串，接着检查这三个字符是否互不相同。
• 字符对比：由于子字符串长度固定为 3，只需比较这三个字符两两是否不同即可，无需使用额外的数据结构。

关键步骤

1. 边界情况处理：若字符串长度小于 3，直接返回 0，因为不存在符合条件的子字符串。
2. 遍历字符串：借助循环从每个可能的起始位置提取长度为 3 的子字符串。
3. 字符唯一性验证：检查三个字符是否满足 a != b && a != c && b != c 的条件。

代码实现

class Solution {
    public int countGoodSubstrings(String s) {
        int n = s.length();
        if (n < 3) return 0;
        
        int count = 0;
        for (int i = 0; i <= n - 3; i++) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            char c = s.charAt(i + 2);
            if (a != b && a != c && b != c) {
                count++;
            }
        }
        return count;
    }
}

代码详细解读

1. 输入长度判断：

   int n = s.length();
   if (n < 3) return 0;
   

   • 先获取字符串 s 的长度 n。
   • 若字符串长度不足 3，直接返回 0，因为无法构成符合要求的子字符串。

2. 初始化计数器：

   int count = 0;
   

   • 定义变量 count 来记录符合条件的子字符串数量，初始值设为 0。

3. 遍历并提取子字符串：

   for (int i = 0; i <= n - 3; i++) {
       char a = s.charAt(i);
       char b = s.charAt(i + 1);
       char c = s.charAt(i + 2);
   

   • 循环从索引 0 开始，到 n - 3 结束，这样能保证每次都能提取到长度为 3 的子字符串。
   • 通过 charAt 方法分别获取当前子字符串的三个字符 a、b、c。

4. 字符唯一性检查：

   if (a != b && a != c && b != c) {
       count++;
   }
   

   • 当这三个字符两两都不相等时，说明该子字符串是 “好子字符串”，此时将计数器 count 加 1。

5. 返回结果：

   return count;
   

   • 循环结束后，返回统计得到的符合条件的子字符串数量。

复杂度分析

• 时间复杂度：，其中 n 是字符串 s 的长度。
  • 只需对字符串进行一次遍历，每个字符的处理操作都是常数时间。
• 空间复杂度：。
  • 除了几个用于存储字符和计数器的变量外，没有使用额外的空间。

总结与优化

1. 算法优势：

   • 该算法无需复杂的逻辑，直接通过遍历和简单的字符比较来解决问题，代码简洁且容易理解。
   • 时间复杂度为线性级别，在处理大规模输入时也能保持较高效率。

2. 扩展思考：

   • 如果题目要求找出长度不固定的无重复字符子字符串，可以考虑使用滑动窗口算法。
   • 若字符集的范围较大（例如包含 Unicode 字符），可以改用哈希集合或字典来记录字符的出现情况。

3. 注意事项：

   • 要确保循环的边界条件正确，避免出现数组越界的错误。
   • 进行字符比较时，要保证所有可能的两两组合都被检查到。