Q8 PepCoding | Smallest Substring Of A String Containing All Characters Of Another String | leetcode76
Tue Jan 24 2023 11:01:01 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public String minWindow(String s, String t) {
if(s.length() < t.length())
return "";
//2 HM to keep track of characters & answer string
HashMap<Character,Integer> map1 = new HashMap<>();
HashMap<Character,Integer> map2 = new HashMap<>();
String ans = "";
//pointers to keep track of window
int i = 0 , j = 0;
//keeping two pointers to keep check of when no. of characters will be the same
int dcc = t.length(); //desired character count
int ccc = 0; //current character count
//frequency map of 2nd string
for(char ch : t.toCharArray())
map2.put(ch , map2.getOrDefault(ch,0)+1);
//acquiring and releasing while traversing the array
for(i = 0 ; i< s.length(); i++){
//storing in map and updating ccc
char ch = s.charAt(i);
map1.put(ch,map1.getOrDefault(ch,0)+1);
if(map1.get(ch) <= map2.getOrDefault(ch,0))
ccc++;
//now that we have valid substring we will store this and check for smaller
//substring by removing character from behind one by one
while(ccc == dcc){
String pans = s.substring(j , i+1); //potential answer
//if its the first answer or if we get a samller answer
if(ans.length()== 0 || pans.length() < ans.length())
ans = pans;
//removing character & updating ccc
char temp = s.charAt(j);
//updating ccc
if(map1.get(temp) <= map2.getOrDefault(temp,0))
ccc--;
if(map1.get(temp) == 1)
map1.remove(temp);
else
map1.put(temp , map1.get(temp)-1);
j++;
}
}
return ans;
}
}
content_copyCOPY
https://leetcode.com/problems/minimum-window-substring/description/
Comments