Contest 416 || Ques-3 || Sliding window🔥
Approach and Intuition:\n\nThe problem asks to count valid substrings of source such that the frequency of every character in the substring is greater than or e
### Approach and Intuition:\n\nThe problem asks to count valid substrings of `source` such that the frequency of every character in the substring is greater than or equal to the frequency of the corresponding character in `target`.\n\n1. **Frequency Count for `target`:**  \n   We first create a frequency array `targetFreq` for the string `target`. This array will store the count of each character in `target`.\n\n2. **Sliding Window to Count Valid Substrings:**  \n   We use a sliding window approach to find valid substrings in `source`. The window expands by moving the `end` pointer and contracts by moving the `start` pointer.\n\n   - For every character `end` in `source`, we increment its frequency in `currentFreq` (a frequency array for the current window).\n   - We check if the current window is valid, i.e., if all characters in the window meet or exceed the frequency requirement set by `targetFreq`.\n   - If valid, every suffix starting at `start` and ending after `end` is valid, so we add `(source.length() - end)` to the result.\n   - We then increment `start` to try finding other possible substrings that could be valid.\n\n3. **Termination of Sliding Window:**  \n   The window contracts by incrementing `start` and decrementing the frequency of the character at the `start` position in `currentFreq`. We continue shrinking the window until it becomes invalid again.\n\n### Time Complexity:\n\n- **Creating the Frequency Array for `target`:**  \n  This takes `O(m)` time where `m` is the length of `target`.\n\n- **Sliding Window Over `source`:**  \n  In the worst case, the `start` pointer is moved at most once for each character in `source`, resulting in `O(n)` complexity where `n` is the length of `source`.  \n  Inside the loop, we check for validity by iterating over the 26 letters (constant time operation). Therefore, the complexity of checking whether the window is valid is `O(26)`, which is treated as `O(1)`.\n\n- **Overall Time Complexity:**  \n  The total time complexity is `O(n + m)` where `n` is the length of `source` and `m` is the length of `target`, because we process both strings once.\n\n### Space Complexity:\n\n- We use two frequency arrays (`targetFreq` and `currentFreq`), both of size 26 (constant space).\n- Hence, the space complexity is `O(1)` (constant space).\n\n# Code\n```java []\nclass Solution {\n    public long validSubstringCount(String source, String target) {\n\n        int[] targetFreq = new int[26];\n        for (int i = 0; i < target.length(); i++) {\n            char c = target.charAt(i);\n            targetFreq[c - \'a\']++;\n        }\n\n        int start = 0;\n        int[] currentFreq = new int[26];\n        long validSubstrings = 0;\n        for (int end = 0; end < source.length(); end++) {\n\n            int charIndex = source.charAt(end) - \'a\';\n            currentFreq[charIndex]++;\n\n            boolean isValid = true;\n            for (int j = 0; j < 26; j++) {\n                if (targetFreq[j] > currentFreq[j]) {\n                    isValid = false;\n                    break;\n                }\n            }\n\n            while (isValid) {\n                validSubstrings += (long) (source.length() - end);\n                charIndex = source.charAt(start) - \'a\';\n                currentFreq[charIndex]--;\n                start++;\n\n                isValid = true;\n                for (int j = 0; j < 26; j++) {\n                    if (targetFreq[j] > currentFreq[j]) {\n                        isValid = false;\n                        break;\n                    }\n                }\n            }\n        }\n        return validSubstrings;\n    }\n}\n\n```
['Sliding Window', 'Java']