LeetCode LCR 017. 最小覆盖子串

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

✅ LCR 017. 最小覆盖子串

思路分析

解法一：滑动窗口（推荐）

核心思路：

与第 3 题（无重复子串）的简单滑动窗口不同，此题需要找最小覆盖，采用”先扩张直到满足条件，再收缩求最小”的模式。

维护两个哈希表：need 记录 t 中每个字符需要的次数，window 记录当前窗口中各字符的实际次数

用 valid 计数器追踪当前满足需求的字符种数（当 window[c] == need[c] 时 valid++），避免频繁遍历哈希表，保持 O(1) 判断

右指针持续扩张窗口，当 valid == len(need) 即窗口已覆盖 t 时，记录候选答案，然后左指针不断收缩直到不满足条件，再继续扩张

每个字符最多进出窗口一次，整体线性时间

复杂度分析：

时间复杂度：O(n + m)，其中 n 为字符串 s 的长度，m 为字符串 t 的长度

空间复杂度：O( Σ )，其中 Σ 为字符集大小，哈希表最多存储 Σ 个字符

class Solution {
    public String minWindow(String s, String t) {
        // 记录 t 中每个字符的需求次数
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.merge(c, 1, Integer::sum);
        }

        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        // valid 表示窗口中已满足需求的字符种数
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            // 右指针扩张窗口
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                window.merge(c, 1, Integer::sum);
                // 该字符恰好满足需求时，valid 加一
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 窗口已覆盖 t，尝试收缩左指针
            while (valid == need.size()) {
                // 更新最小覆盖子串
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                // 左指针收缩，移出字符
                char d = s.charAt(left++);
                if (need.containsKey(d)) {
                    // 移出前恰好满足需求，移出后不满足，valid 减一
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.merge(d, -1, Integer::sum);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

func minWindow(s string, t string) string {
    // 记录 t 中每个字符的需求次数
    need := map[byte]int{}
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    window := map[byte]int{}
    left, right := 0, 0
    // valid 表示窗口中已满足需求的字符种数
    valid := 0
    start := 0
    length := len(s) + 1

    for right < len(s) {
        // 右指针扩张窗口
        c := s[right]
        right++

        if _, ok := need[c]; ok {
            window[c]++
            // 该字符恰好满足需求时，valid 加一
            if window[c] == need[c] {
                valid++
            }
        }

        // 窗口已覆盖 t，尝试收缩左指针
        for valid == len(need) {
            // 更新最小覆盖子串
            if right-left < length {
                start = left
                length = right - left
            }

            // 左指针收缩，移出字符
            d := s[left]
            left++

            if _, ok := need[d]; ok {
                // 移出前恰好满足需求，移出后不满足，valid 减一
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

    if length == len(s)+1 {
        return ""
    }
    return s[start : start+length]
}

相似题目

题目	难度	考察点
3. 无重复字符的最长子串	中等	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
567. 字符串的排列	中等	滑动窗口
239. 滑动窗口最大值	困难	单调队列
30. 串联所有单词的子串	困难	滑动窗口
209. 长度最小的子数组	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/17896345