Sliding window, explained
Approach\nA valid substring of word1 should have all characters from word2 plus maybe some more. Let\'s think of word1 this way:\n\n\nword1 = prefix + word2 + p
# Approach\nA valid substring of `word1` should have all characters from `word2` plus *maybe* some more. Let\'s think of `word1` this way:\n\n```\nword1 = prefix + word2 + postfix\n```\nLet\'s check all the substrings starting from some point in `word1`. As soon as we get the first valid `prefix + word2` substring, then ALL the substrings till the rest of the `word1` are valid too, so we add the postfix length the the resulting sum. And while we have enough characters to form `word2` we can shrink `prefix` part char by char each time getting a new substring set.\n\nSo, let\'s use sliding window approach, increasing the window size till we find a valid substring, then shrinking the window till it\'s no longer valid.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(1)$$\n\n# Code\n```csharp []\npublic class Solution\n{\n    public long ValidSubstringCount(string word1, string word2)\n    {\n        var required = new char[26];\n        foreach (char c in word2)\n        {\n            required[c - \'a\']++;\n        }\n\n        int n = word1.Length;\n        int l = 0;\n        int r = 0;\n        var window = new char[26];\n        long sum = 0;\n\n        while (r < n)\n        {\n            window[word1[r] - \'a\']++;\n            \n            while (l < n && IsWindowValid(window, required))\n            {\n                sum += n - r;\n                window[word1[l] - \'a\']--;\n                l++;\n            }\n\n            r++;\n        }\n\n        return sum;\n    }\n\n    private bool IsWindowValid(char[] window, char[] required)\n    {\n        for (var i = 0; i < window.Length; i++)\n        {\n            if (window[i] < required[i]) return false;\n        }\n        return true;\n    }\n}\n```
['String', 'Sliding Window', 'Counting Sort', 'C#']