// 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".

// Note:

// 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 there will always be only one unique minimum window in S.

public class Solution {

public String minWindow(String s, String t) {

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

for(char c : s.toCharArray()) {

map.put(c, 0);

}

for(char c : t.toCharArray()) {

if(map.containsKey(c)) {

map.put(c, map.get(c)+ 1);

}

else {

return "";

}

}

int start = 0;

int end = 0;

int minStart = 0;

int minLength = Integer.MAX_VALUE;

int counter = t.length();

while(end < s.length()) {

char c1 = s.charAt(end);

if(map.get(c1) > 0) {

counter--;

}

map.put(c1, map.get(c1) - 1);

end++;

while(counter == 0) {

if(minLength > end - start) {

minLength = end - start;

minStart = start;

}

char c2 = s.charAt(start);

map.put(c2, map.get(c2) + 1);

if(map.get(c2) > 0) {

counter++;

}

start++;

}

}

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

}

}