Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC". If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such windows, you are guaranteed that …

MinWindowSubString.java

public String minWindow(String s, String t) {      
    Map<Character, Integer> map = new HashMap<>();

    for(Character ch : t.toCharArray())
        map.put(ch, map.getOrDefault(ch, 0) + 1);

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

    while(end < s.length()) {
        if(map.getOrDefault(s.charAt(end), 0) > 0)
            toBeFound--;

        map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) - 1);
        end++;

        while(toBeFound == 0) {
            if(end - start < minLen) {
                minStart = start;
                minLen = end - start;
            }

            map.put(s.charAt(start), map.getOrDefault(s.charAt(start), 0) + 1);
            if(map.getOrDefault(s.charAt(start), 0) > 0)
                    toBeFound++;

            start++;
        }
    }

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