76. Minimum Window Substring

/**
 * Sliding Window
 *
 * Time Complexity: O(S + T)
 *
 * Space Commplexity: O(S)
 *
 * S = length of String S. T = length of String T
 */
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }

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

        // Adding all characters in string S in the map with count 0. This will help us
        // to return early if string T contains characters not present in string S.
        for (char c : s.toCharArray()) {
            map.put(c, 0);
        }

        // Adding all characters in string T in the map with their count.
        for (char c : t.toCharArray()) {
            if (!map.containsKey(c)) {
                return "";
            }
            map.put(c, map.get(c) + 1);
        }

        int charTLeft = t.length();
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        int start = 0;
        int end = 0;

        // Sliding Window
        while (end < s.length()) {
            char sEnd = s.charAt(end);
            if (map.get(sEnd) > 0) {
                charTLeft--;
            }
            map.put(sEnd, map.get(sEnd) - 1);

            while (charTLeft == 0) {
                if (minLen > end - start + 1) {
                    minLen = end - start + 1;
                    minStart = start;
                }
                char sStart = s.charAt(start);
                map.put(sStart, map.get(sStart) + 1);
                if (map.get(sStart) > 0) {
                    charTLeft++;
                }
                start++;
            }

            end++;
        }

        if (minLen == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(minStart, minStart + minLen);
    }
}

/**
 * Sliding Window. This solution adds an optimization for very long string S
 * when compared to string T. Also string S contains lot of characters not in T.
 *
 * Time Complexity: O(S + T)
 *
 * Space Commplexity: O(S + T)
 *
 * S = length of String S. T = length of String T
 */
import javafx.util.Pair;
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }

        Map<Character, Integer> map = new HashMap();
        // Adding all characters in string T in the map with their count.
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        List<Pair<Integer, Character>> filteredS = new ArrayList();
        // Creating a new list with characters in S that are present in T too.
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                filteredS.add(new Pair<Integer, Character>(i, c));
            }
        }

        int charTLeft = t.length();
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        int start = 0;
        int end = 0;

        // Sliding Window
        while (end < filteredS.size()) {
            Pair<Integer, Character> endPair = filteredS.get(end);
            int endPairIdx = endPair.getKey();
            char endPairChar = endPair.getValue();

            if (map.get(endPairChar) > 0) {
                charTLeft--;
            }
            map.put(endPairChar, map.get(endPairChar) - 1);

            while (charTLeft == 0) {
                Pair<Integer, Character> startPair = filteredS.get(start);
                int startPairIdx = startPair.getKey();
                char startPairChar = startPair.getValue();

                if (minLen > endPairIdx - startPairIdx + 1) {
                    minLen = endPairIdx - startPairIdx + 1;
                    minStart = startPairIdx;
                }

                map.put(startPairChar, map.get(startPairChar) + 1);
                if (map.get(startPairChar) > 0) {
                    charTLeft++;
                }
                start++;
            }

            end++;
        }

        if (minLen == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(minStart, minStart + minLen);
    }
}