【滑动窗口】LCR 017. 最小覆盖子串

LCR 017. 最小覆盖子串

解题思路

• need 记录满足条件的实际有效字符
• window记录当前窗口内的所有字符
• 遍历s 针对每一个字符送入window 计算valid 满足条件的有效字符个数
• 判断valid和need的尺寸 判断窗口是否需要收缩
• 如果需要收缩，计算窗口的长度，更新start 和 minLen
• 最后 如果左边字符在window中 移除该字符

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        // 初始化need
        for (int i = 0; i < t.length(); i++) {
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }

        int left = 0;
        int right = 0;
        int valid = 0; // 记录窗口满足条件的有效字符个数
        int start = 0; // 最小窗口的起始位置
        int minLength = Integer.MAX_VALUE; // 最小窗口的长度

        while (right < s.length()) {
            char c = s.charAt(right);
            right++;

            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);

                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 判断是否需要收缩
            while (valid == need.size()) {
                // 更新最小窗口信息
                if (right - left < minLength) {
                    start = left;
                    minLength = right - left;
                }

                char d = s.charAt(left);
                left++;

                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }

                    window.put(d, window.get(d) - 1);
                }
            }
        }

        if (minLength == Integer.MAX_VALUE) {
            return "";
        } else {
            return s.substring(start, start + minLength);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58