Minimum Window Substring

1public String minWindow(String s, String t) {
2    Map<Character, Integer> targetMap = new HashMap<>();
3    for (char c : t.toCharArray()) {
4        targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
5    }
6
7    int minLen = Integer.MAX_VALUE;
8    int left = 0;
9    Map<Character, Integer> windowMap = new HashMap<>();
10    int formed = 0;
11    int required = targetMap.size();
12    int minStart = 0;
13
14    for (int right = 0; right < s.length(); right++) {
15        char c = s.charAt(right);
16        windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
17
18        if (targetMap.containsKey(c) &&
19            windowMap.get(c).intValue() == targetMap.get(c).intValue()) {
20            formed++;
21        }
22
23        while (formed == required && left <= right) {
24            if (right - left + 1 < minLen) {
25                minLen = right - left + 1;
26                minStart = left;
27            }
28
29            char leftChar = s.charAt(left);
30            windowMap.put(leftChar, windowMap.get(leftChar) - 1);
31
32            if (targetMap.containsKey(leftChar) &&
33                windowMap.get(leftChar) < targetMap.get(leftChar)) {
34                formed--;
35            }
36
37            left++;
38        }
39    }
40
41    if (minLen == Integer.MAX_VALUE) {
42        return "";
43    } else {
44        return s.substring(minStart, minStart + minLen);
45    }
46}