Leetcode-Java/0076. Minimum Window Substring at main · Hoaru/Leetcode-Java · GitHub

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
class Solution {
    public static String minWindow(String s, String t) {
        System.out.println(s.length());
        System.out.println(t.length());
        if(s.length() < t.length() || s == "" || t == "") return "";
        HashMap<Character, Integer> mapt = new HashMap<>();
        HashMap<Character, Integer> mapw = new HashMap<>();
        for(char c: t.toCharArray()){
            mapt.put(c, mapt.getOrDefault(c, 0) + 1);
        }
        int required = mapt.size(), satisfied = 0;
        int start = 0, minLen = Integer.MAX_VALUE;
        int left = 0, right = 0;
        while(right < s.length()){
            char c1 = s.charAt(right);
            mapw.put(c1, mapw.getOrDefault(c1, 0) + 1);
            if(mapt.containsKey(c1) && mapw.get(c1).intValue() == mapt.get(c1).intValue()) {
                satisfied ++;
            }
            while(left <= right && satisfied == required) {
                int currLen = right - left + 1;
                if(currLen < minLen) {
                    minLen = currLen;
                    start = left;
                }
                char c2 = s.charAt(left);
                mapw.put(c2, mapw.get(c2) - 1);
                if(mapt.containsKey(c2) && mapw.get(c2).intValue() < mapt.get(c2).intValue()) {
                    satisfied --;
                }
                left++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}