Simple Explanation with Images - Java
Intuition\n# Approach\n Describe your approach to solving the problem. \n\nHere\u2019s a clearer version of your explanation:\n\n"Start by identifying the windo
# Intuition\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nHere\u2019s a clearer version of your explanation:\n\n"Start by identifying the window that contains all the characters of `word2`. Then, begin shrinking the left boundary of the window while ensuring that the condition still holds. When the condition breaks, you\u2019ve found the minimal window that meets the criteria.\n\nAt this point, calculate the number of possible subarrays starting to the left (`leftCount`) and the number of possible subarrays to the right (`rightCount`). Multiply these two values (`leftCount * rightCount`) to determine the total number of subarrays that can be formed with this minimal window.\n\nNext, continue searching for additional minimal windows by shrinking the left boundary further. Since most of the combinations have already been accounted for in the previous calculation, you only need to focus on new possibilities."\n\n![Screenshot 2024-09-23 at 9.01.58\u202FPM.png](https://assets.leetcode.com/users/images/47bb31c1-0347-4327-b7ba-e44e74e35dbb_1727105530.2036881.png)\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public long validSubstringCount(String word1, String word2) {\n        int word1Len = word1.length();\n        int[] word2Freq = new int[26];\n        Arrays.fill(word2Freq,0);\n        for(char c : word2.toCharArray()){\n            word2Freq[c-\'a\']++;\n        }\n        long ans = 0;\n        int[] word1Freq = new int[26];\n        Arrays.fill(word1Freq,0);\n        int leftBorder = 0;\n        int left = 0,right = 0;\n        while(left < word1Len && right < word1Len){\n            while(!doesSatisfyWordFreq(word2Freq,word1Freq) && right < word1Len){\n                word1Freq[word1.charAt(right)-\'a\']++;\n                ++right;\n                if(doesSatisfyWordFreq(word2Freq,word1Freq))break;\n            }\n            if(!doesSatisfyWordFreq(word2Freq,word1Freq))break;\n            while(doesSatisfyWordFreq(word2Freq,word1Freq) && left < word1Len){\n                word1Freq[word1.charAt(left)-\'a\']--;\n                ++left;\n                if(!doesSatisfyWordFreq(word2Freq,word1Freq))break;\n            }\n            int leftStartPoints = left - leftBorder;\n            int rightPoints = word1Len - right + 1;\n            long possibilities = (long)leftStartPoints*rightPoints;\n            ans += possibilities;\n            leftBorder = left;\n        }\n        return ans;\n    }\n    private boolean doesSatisfyWordFreq(int[] word2Freq,int[] word1Freq){\n        for(int i = 0;i< 26;++i){\n            if(word2Freq[i] > word1Freq[i])return false;\n        }\n        return true;\n    }\n}\n```
['Java']