leetcode
leetcode 1651 ~ 1700
长度为三且各字符不同的子字符串

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

难度:

标签:

题目描述

代码结果

运行时间: 19 ms, 内存: 16.1 MB


/*
 * 思路:
 * 1. 使用Java Stream API简化遍历和过滤的过程。
 * 2. 使用range和filter函数筛选出所有长度为3的好子字符串。
 */
import java.util.stream.IntStream;

public class GoodSubstringStream {
    public int countGoodSubstrings(String s) {
        return (int) IntStream.range(0, s.length() - 2)
                .mapToObj(i -> s.substring(i, i + 3))
                .filter(sub -> sub.chars().distinct().count() == 3)
                .count();
    }
}

解释

方法:

该题解采用滑动窗口的方法来解决问题。首先检查字符串长度是否小于3,因为长度小于3的字符串无法形成长度为3的子字符串。如果长度足够,使用一个哈希表(使用defaultdict(int))来记录当前窗口内各字符的出现次数。初始化哈希表时,先将前两个字符的计数加入。随后,从索引2开始遍历字符串s,每次将新字符加入计数,并检查当前窗口(即最后三个字符)是否为好字符串,即哈希表的长度是否为3。如果是,计数器增加。接着,将窗口最左边的字符计数减一,如果减到0,则从哈希表中移除该字符。这样可以确保哈希表始终对应当前考察的窗口。最后返回计数器的值。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在判断好子字符串时,只检查哈希表的长度是否为3而不是其他条件?
在这个问题中,我们需要判断的子字符串长度固定为3,且要求这三个字符彼此不同。使用哈希表记录窗口内每个字符的出现次数,如果哈希表的长度为3,这意味着窗口内有三个不同的字符,每个字符出现一次,完全符合好子字符串的定义。检查哈希表长度是否为3是一个有效且简洁的方法来确认当前窗口是否为好子字符串。如果检查其他条件,如每个字符的具体出现次数,将是不必要的,因为长度为3的窗口且哈希表长度为3已经隐含了每个字符只出现一次。
🦆
在滑动窗口的实现中,当窗口的左边界字符计数减到0时立即删除该字符的原因是什么?
在滑动窗口算法中,保持哈希表的准确性和精简性是非常重要的。当窗口向右移动时,最左边的字符应该从当前考察的窗口中移除。如果这个字符的计数减到0,意味着它不再在当前的窗口中出现。删除这个计数为0的字符可以确保哈希表只包含当前窗口中存在的字符,这样可以减少内存使用,并且使得哈希表的操作更加高效,同时也便于正确判断窗口内字符的种类数量。
🦆
在实际的LeetCode环境中,是否需要考虑线程安全或并发修改哈希表的问题?
在LeetCode这样的编程竞赛和面试准备平台中,通常的假设是代码执行环境是单线程的。因此,不需要考虑线程安全或哈希表的并发修改问题。每次提交的代码都是在一个独立的环境中运行,处理单个输入实例。在这种情况下,使用常规的数据结构如哈希表等不需要额外的同步机制或并发控制措施。
🦆
如果输入字符串`s`长度正好为3,这种情况下的逻辑处理是否存在潜在的问题或需要额外的处理?
如果输入字符串`s`的长度正好为3,当前的逻辑处理是合适的,不需要额外的处理。根据题解,初始化时哈希表包含前两个字符,然后从索引2开始遍历字符串,这意味着会考察整个字符串作为一个单独的窗口。在这种情况下,只要这三个字符互不相同,就会正确地计数为一个好子字符串。因此,对于长度正好为3的字符串,算法已经能够正确处理,无需修改。

相关问题