TonyKim9401.java

// TC: O(n)
// using two pointer lef and right, it visits all elements only once each.
// SC: O(n + m)
// 2 hashmap used for checking the given Strings s and t, n is the size of s, m is the size of m
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();

        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int required = map.size();
        int formed = 0;

        int left = 0;
        int right = 0;
        int[] ans = {-1, 0, 0};

        Map<Character, Integer> windowCounts = new HashMap<>();

        while (right < s.length()) {
            char c = s.charAt(right);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);

            if (map.containsKey(c) &&
                    windowCounts.get(c).intValue() == map.get(c).intValue()) {
                formed += 1;
            }

            while (left <= right && formed == required) {
                c = s.charAt(left);

                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }

                windowCounts.put(c, windowCounts.get(c) - 1);
                if (map.containsKey(c) &&
                        windowCounts.get(c).intValue() < map.get(c).intValue()) {
                    formed -= 1;
                }

                left += 1;
            }
            right += 1;
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}