长度为三且各字符不同的子字符串
难度:
标签:
题目描述
代码结果
运行时间: 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而不是其他条件?
▷🦆
在滑动窗口的实现中,当窗口的左边界字符计数减到0时立即删除该字符的原因是什么?
▷🦆
在实际的LeetCode环境中,是否需要考虑线程安全或并发修改哈希表的问题?
▷🦆
如果输入字符串`s`长度正好为3,这种情况下的逻辑处理是否存在潜在的问题或需要额外的处理?
▷