leetcode
leetcode 951 ~ 1000
长度为 K 的无重复字符子串

长度为 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时只记录一次子串并立即缩小窗口,没有考虑继续维持窗口大小为K来探索后续可能的子串。这可能需要更细致的窗口滑动处理来捕捉所有可能的子串。
🦆
在处理窗口中的重复字符时,为什么选择删除左侧字符直到不再有重复,这种方法与直接将左指针移动到重复字符的下一个位置有何不同?
选择删除左侧字符直到不再有重复的方法可以细致地控制窗口内的字符组成,确保每一步都尝试形成有效的子串。而直接将左指针移动到重复字符的下一个位置虽然简单,但可能跳过某些有效的子串的组合,因为这种跳跃式的移动会使窗口中间的其他字符组合未被充分考虑。逐个移除左侧字符的方法提供了更多的灵活性和可能性,以找到所有的有效子串。
🦆
为什么题解中在窗口中字符达到K时仅增加计数并移动左指针一次,而不考虑继续保持窗口大小为K继续探索后续可能的子串?
题解中这样处理主要是为了简化操作和逻辑。每次窗口达到K时记录一次有效子串,然后通过移动左指针来探索新的可能性,这样可以避免复杂的窗口管理。虽然这种方法可能会错过一些子串,但总体上可以有效地找到大部分有效子串。要完全不错过任何可能的子串,可以采用更复杂的窗口调整策略,如在每个右指针移动后都检查从当前左指针开始的所有长度为K的窗口。

相关问题