长度为 K 的无重复字符子串
难度:
标签:
题目描述
代码结果
运行时间: 36 ms, 内存: 16.2 MB
/*
* Problem: Find all substrings of length K with no repeating characters using Java Streams.
* Approach:
* 1. Generate all possible substrings of length K using IntStream.
* 2. Filter substrings that have unique characters by checking their set size.
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public List<String> numKLenSubstrNoRepeats(String S, int K) {
if (S.length() < K) return Collections.emptyList();
return IntStream.rangeClosed(0, S.length() - K)
.mapToObj(i -> S.substring(i, i + K))
.filter(sub -> sub.chars().distinct().count() == K)
.collect(Collectors.toList());
}
}
解释
方法:
此题解采用了滑动窗口的方法来寻找长度为 K 且不包含重复字符的子串。定义两个指针 left 和 right 表示窗口的左右边界。使用一个字典 seen 来记录当前窗口中字符的最新位置。当窗口中的字符数达到 K 且没有重复时,此窗口为一个有效的子串。每次当窗口有效时,计数加一,并向右滑动窗口。如果遇到重复字符,则调整左指针直到该重复字符被排除出窗口。
时间复杂度:
O(n)
空间复杂度:
O(min(n, k))
代码细节讲解
🦆
为什么在发现重复字符时,需要通过移动左指针来排除重复,而不是直接跳过这个重复的字符或重置窗口?
▷🦆
题解中提到如果窗口大小达到K时,就记录一个有效子串并移除窗口最左边的字符。这种处理方式是否意味着我们可能错过某些有效的长度为K的子串?
▷🦆
在处理窗口中的重复字符时,为什么选择删除左侧字符直到不再有重复,这种方法与直接将左指针移动到重复字符的下一个位置有何不同?
▷🦆
为什么题解中在窗口中字符达到K时仅增加计数并移动左指针一次,而不考虑继续保持窗口大小为K继续探索后续可能的子串?
▷