Q8 PepCoding | Smallest Substring Of A String Containing All Characters Of Another String | leetcode76

PHOTO EMBED

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/