I am working on this problem.
I have implemented my appraoch as given below. It is giving me partially correct answer. Can you please help. I have tried so many examples, not able to figure out the problem.
public class Solution {
public String minWindow(String A, String B) {
//hm contains the String B character's frequency
//horg denotes no. of distinct elements in String B
HashMap<Character, Integer> hm = new HashMap<>();
HashSet<Character> horg = new HashSet<>();
int m = B.length();
for(int i=0;i<m;i++){
horg.add(B.charAt(i));
hm.put(B.charAt(i), hm.getOrDefault(B.charAt(i),0)+1 );
}
//hm and horg is filled
int l = 0;
int r = 0;
int n = A.length();
int size = n;
String ans = "";
HashMap<Character, Integer> wind = new HashMap<>();
HashSet<Character> hs = new HashSet<>();
//wind contains the current window character frequency(only those present in B)
//hs will contains all characters in B that is appeared, (means lets say x in hs,
// we dont care if we encounter more no. of character as we h
//enough no. of character of x to be present in String B)
while(r<n){
//inrease the window
while(r<n && hs.size()<horg.size()){
char x = A.charAt(r);
if(hm.containsKey(x)){
wind.put(x, wind.getOrDefault(x,0)+1);
if(wind.get(x)==hm.get(x)){
hs.add(x);
}
}
r++;
}
//squeez the window
while(hs.size()==horg.size() ){
char y = A.charAt(l);
if(hm.containsKey(y)){
if(wind.get(y)==1){
wind.remove(y);
hs.remove(y);
}else{
wind.put(y, wind.get(y)-1 );
if(wind.get(y)<hm.get(y)){
hs.remove(y);
}
}
}
l++;
}
if(size>r-l){
size=r-l;
ans = A.substring(l-1,r);
}
}
return ans;
}
}
/*
S = "ADOBECODEBANC"
T = "ABC"
|
ADOBEACODEBANC
|
*/