50 DSA-Questions: #17

#17. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

public class Exercise17 {
    // private final String INPUT = "ADOBECODEBANC"; // "BANC" contains A, B and C
    // private final String INPUT = "CANADABANCNOTE"; // "BANC" contains A, B and C
    // private final String INPUT = "BACUL"; // "BANC" contains A, B and C
    // private final String INPUT = "ABBEACOBATR"; // "BEAC" contains A, B and C
    // private final String SEARCH = "ABC";

    private final String INPUT = "ABBEACOBATR"; // "BBEAC" contains A, B, B and C
    private final String SEARCH = "ABBC";

    private boolean canCompare(Map<Character, Integer> map) {
        return map.size() == SEARCH.length();
    }

    private int getMin(Map<Character, Integer> map) {
        return map.values().stream().min(Integer::compare).get();
    }

    private int getMax(Map<Character, Integer> map) {
        return map.values().stream().max(Integer::compare).get();
    }

    private void solveWithoutDuplicates() {
        Map<Character, Integer> map = new HashMap<>();

        int minDist = Integer.MAX_VALUE;
        String substr = "";

        int max, min;

        for (int i=0; i<INPUT.length(); i++) {
            char key = INPUT.charAt(i);
            if (SEARCH.indexOf(key) >= 0) {
                map.put(key, i);
                min = getMin(map);
                max = getMax(map);

                if (canCompare(map)) {
                    int distance = max - min;
                    if (distance < minDist) {
                        minDist = distance;
                        substr = INPUT.substring(min, max + 1);
                    }
                }
            }
        }

        System.out.println(substr);
    }

    public static void main(String args[]) {
        new Exercise17().solveWithoutDuplicates();
    }