Sliding Window || Beats 100% || My experience
Intuition\nTo be honest, the problem itself wasn\u2019t too difficult to understand, and the intuition came fairly quickly. The real challenge lay in handling s
# Intuition\nTo be honest, the problem itself wasn\u2019t too difficult to understand, and the intuition came fairly quickly. The real challenge lay in handling some of the edge cases. It took me over two hours to solve it on my own. If you\u2019ve solved a few sliding window problems before, grasping the intuition is straightforward. Essentially, we maintain a window while continuously checking the frequency of elements. After each character, we verify whether the current window contains the required characters or not.\n-\n\n# Approach\nI recommend you guys to solve few easy problems on sliding window before solving this. Because even i would have felt it tough if i hadn\'t solved few problems long back\n\n1. **Initial Check**: First, we check if the length of `word1` is smaller than `word2`. If it is, we return `0` because it\'s impossible for `word1` to contain `word2` as a substring.\n\n2. **Set Up Arrays**: We convert both `word1` and `word2` into arrays of characters. Then, we create two arrays of size 26 (for each letter of the alphabet):\n   - `freq`: To store the frequency of each character in `word2`.\n   - `window`: To track the frequency of characters in a sliding window within `word1`.\n\n3. **Count Matching Characters**: We initialize two counters:\n   - `count`: To track how many characters in the current window of `word1` match those in `word2`.\n   - `strCount`: To keep the final count of valid substrings.\n\n4. **Sliding Window Approach**:\n   - For each character in `word1`, we move the window forward one character at a time.\n   - If the character at the current position exists in `word2` and hasn\u2019t yet reached the required frequency in the window, we increase the `count`.\n   - Add the current character to the window\'s frequency count.\n\n5. **Check Valid Substrings**:\n   - Once the `count` matches the length of `word2` (i.e., the window contains all characters of `word2`), we add the remaining characters from the current position to the end of `word1` to `strCount`.\n   - Then, we slide the window from the left by reducing the frequency of the character at the start of the window and adjusting the `count` accordingly.\n\n6. **Final Return**: After the loop ends, `strCount` holds the total number of valid substrings where `word2` appears in `word1`, and this value is returned.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```java []\nclass Solution {\n    public long validSubstringCount(String word1, String word2) {\n        if (word1.length() < word2.length())\n            return 0;\n\n        char[] w1 = word1.toCharArray(), w2 = word2.toCharArray();\n        int[] freq = new int[26];\n\n        for (char c : w2)\n            freq[c - \'a\']++;\n\n        int[] window = new int[26];\n        long count = 0;\n\n        long strCount = 0;\n        int j = 0;\n\n        for (int i = 0; i < w1.length; i++) {\n            char c = w1[i];\n\n            if (freq[c - \'a\'] != 0 && window[c - \'a\'] < freq[c - \'a\']) {\n                count++;\n            }\n            window[c - \'a\']++;\n\n            while (count == w2.length && j <= i) {\n                strCount += (w1.length - i);\n\n                window[w1[j] - \'a\']--;\n\n                if (window[w1[j] - \'a\'] < freq[w1[j] - \'a\'])\n                    count--;\n\n                j++;\n            }\n        }\n        return strCount;\n    }\n}\n```
['Two Pointers', 'Sliding Window', 'Java']