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

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

标题形貌

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

焦点思路

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

关键步骤

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

代码实现

1. class Solution {
2.     public int countGoodSubstrings(String s) {
3.         int n = s.length();
4.         if (n < 3) return 0;
5.         
6.         int count = 0;
8.         for (int i = 0; i <= n - 3; i++) {
9.             char a = s.charAt(i);
10.             char b = s.charAt(i + 1);
11.             char c = s.charAt(i + 2);
12.             if (a != b && a != c && b != c) {
13.                 count++;
14.             }
15.         }
16.         return count;
18.     }
19. }

复制代码

代码详细解读

• 输入长度判定：
  
  1. int n = s.length();
  2. if (n < 3) return 0;

  复制代码
  
  
  • 先获取字符串 s 的长度 n。
    
  • 若字符串长度不敷 3，直接返回 0，因为无法构成符合要求的子字符串。
    
  
  
• 初始化计数器：
  
  1. int count = 0;

  复制代码
  
  
  • 界说变量 count 来记载符合条件的子字符串数目，初始值设为 0。
    
  
  
• 遍历并提取子字符串：
  
  1. for (int i = 0; i <= n - 3; i++) {
  2.     char a = s.charAt(i);
  3.     char b = s.charAt(i + 1);
  4.     char c = s.charAt(i + 2);

  复制代码
  
  
  • 循环从索引 0 开始，到 n - 3 结束，这样能包管每次都能提取到长度为 3 的子字符串。
    
  • 通过 charAt 方法分别获取当前子字符串的三个字符 a、b、c。
    
  
  
• 字符唯一性检查：
  
  1. if (a != b && a != c && b != c) {
  2.     count++;
  3. }

  复制代码
  
  
  • 当这三个字符两两都不相等时，说明该子字符串是 “好子字符串”，此时将计数器 count 加 1。
    
  
  
• 返回结果：
  
  1. return count;

  复制代码
  
  
  • 循环结束后，返回统计得到的符合条件的子字符串数目。
    
  
  

复杂度分析

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

总结与优化

• 算法优势：
  
  
  
  • 该算法无需复杂的逻辑，直接通过遍历和简单的字符比较来解决问题，代码简便且容易理解。
    
  • 时间复杂度为线性级别，在处理大规模输入时也能保持较高服从。
    
  
  
• 扩展思索：
  
  
  
  • 如果标题要求找出长度不固定的无重复字符子字符串，可以思量使用滑动窗口算法。
    
  • 若字符集的范围较大（例如包含 Unicode 字符），可以改用哈希集合或字典来记载字符的出现情况。
    
  
  
• 注意事项：
  
  
  
  • 要确保循环的边界条件正确，制止出现数组越界的错误。
    
  • 进行字符比较时，要包管所有大概的两两组合都被检查到。
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。