✅HARD MADE EASY | SLIDING WINDOW | JAVA | Explained🔥🔥🔥
Problem: Find the minimum window substring in string S which will contain all the characters in string T in inclusion and order.\n\nApproach:\n\nWe employ a sli
**Problem**: Find the minimum window substring in string S which will contain all the characters in string T in inclusion and order.\n\n**Approach**:\n\nWe employ a sliding window technique, where we maintain a window of characters in string S.\nA HashMap is used to keep track of the characters in string T and their required frequencies.\nA count variable is used to keep track of the number of characters from T found in the current window.\n\n**Code** **Breakdown**:\n\n**Initialization**:\n\n**i and j**: Pointers representing the start and end of the sliding window.\nminLen: Stores the minimum length of the valid substring found so far.\nmap: A HashMap to store characters and their frequencies from string T.\ncount: To keep track of the number of characters from T found in the current window.\n**startInd:** Stores the starting index of the minimum window.\n\n**Preprocessing:**\n\nPopulate the map with characters from string T and their frequencies.\n\n**Sliding Window:**\n\nWhile j is less than the length of string S:\nIf the current character at index j is in the map and its frequency is greater than 0, increment count.\nDecrement the frequency of the current character in the map.\nIf count equals the length of string T, it means we found a valid window.\nUpdate minLen and startInd if the current window is smaller.\nIncrement the frequency of the character at index i in the map.\nIf the increased frequency becomes greater than 0, it means we can remove this character from the window without affecting the validity. Decrement count.\nIncrement i to shrink the window.\nIncrement j to expand the window.\n\n**Return the result:**\n\nIf a valid window was found, return the substring starting at startInd with length minLen. Otherwise, return an empty string.\n\n**Key Points:**\n\nThe sliding window efficiently explores all possible substrings.\nThe HashMap keeps track of character frequencies from string T.\nThe count variable helps identify valid windows.\nThe code optimizes the process by shrinking the window when possible.\n\n# Code\n```\n// Algo Used: Slinding Window , 2 pounters, Hashing\n// TC: O N , SC : O N\nclass Solution {\n    public String minWindow(String s, String t) {\n         int i= 0;\n        int j= 0;\n        int n= s.length();\n        int m= t.length();\n        int minLen= Integer.MAX_VALUE;;\n        HashMap<Character , Integer> map = new HashMap<>();\n        int count= 0;   // for counting if we have got all the chars from t in our substring\n        int startInd= -1;\n\n        for(int ind = 0 ; ind< m; ind++){   // add all the chars from t in our map\n             map.put(t.charAt(ind) , map.getOrDefault(t.charAt(ind) ,0)+1);\n        }\n        while(j < n){\n             if(map.getOrDefault(s.charAt(j) ,0)>0){    // if curr sbubstring has one of the char from t then increase count by 1 (Note: Imp : In our curr substring only the char which are equal from the t will be > 0 , other then t will be in negative value)\n                count++;\n            }\n            map.put(s.charAt(j) , map.getOrDefault(s.charAt(j),0)-1); // adding in map (which ever value we put , we will reduce it freq)\n            \n            while(count == m){  // jab tak count == k hai chalega, jaisi  count < k  hoga toh break hojayga\n                if(j - i + 1 < minLen){\n                    minLen= j - i + 1;\n                    startInd= i;\n                }\n\n                map.put(s.charAt(i) , map.get(s.charAt(i))+1); // found one of the ans so now shrinking left pointer, so now increase the freq\n                if(map.get(s.charAt(i))>0){  // updating count\n                    count--;\n                }\n                i++;\n            }\n            j++;\n        }\n        if(startInd == -1){\n            return "";\n        }\n        return s.substring(startInd, startInd+minLen);\n    }\n}\n```
['Java']