Sliding Window with explanation and very readable with comments
So this is a pretty common sliding window problem. So one thing that I always see people ask is "how do I recognize a sliding window problem?" Well, there are t
So this is a pretty common sliding window problem. So one thing that I always see people ask is "how do I recognize a sliding window problem?" Well, there are three things to look for:\n1) A question asking you to analyze a contiguous set of data (subarray, substring, etc)\n2) A predefined condition that can be analyzed for each set of data\n3)  The max, min, longest, shortest, number of, etc things that meet the condition.\n\nYou can use the same sliding window algorithms with a couple different variations for almost every sliding window problem. This particular problem requires the use of a dynamically resizing sliding window (one that gets longer until it meets the condition and shrinks until it does not). I left comments for every piece of the code.  It\'s a bit longer than the "concise" answers but I prefer a longer, more readable piece of code over a short and unreadable one.  You could have also used an array to store the character frequencies but I like the hashmap implementation better in terms of readability.\n\nTime Complexity O(N) | Space O(1) since we always going to have three elements stored (a,b,c) and this won\'t change even if our string was a million characters long.\n\n```\nclass Solution {\n    public int numberOfSubstrings(String s) {\n        //use a dynamic sliding window with aux DS\n        Map<Character, Integer> charFreqMap = new HashMap<>();\n        int numSubstrings = 0;\n        int leftWindowIdx = 0;\n        \n        //basic window algorithm set up\n        for(int rightWindowIdx = 0; rightWindowIdx < s.length(); rightWindowIdx++){\n            //increase the window size\n            char rightChar = s.charAt(rightWindowIdx);\n            //add the freq of a,b,c\n            charFreqMap.put(rightChar, charFreqMap.getOrDefault(rightChar, 0) + 1);\n            \n            //if a,b,c freq are all >= 1 we can reduce the window until we break OG condition\n            while(charFreqMap.size() >= 3){\n                //close window and decrease char count for left-most char\n                char leftChar = s.charAt(leftWindowIdx);\n                charFreqMap.put(leftChar, charFreqMap.get(leftChar) - 1);\n                //don\'t forget to remove any empty char count\n                if(charFreqMap.get(leftChar) == 0){\n                    charFreqMap.remove(leftChar);\n                }\n                //close window \n                leftWindowIdx++;\n            }\n            //each idx after closing will be equal to the number of substrings after this idx\n            numSubstrings += leftWindowIdx;\n        }\n        return numSubstrings;\n    }\n}
[]