Given a lowercase string s and a string required of distinct lowercase letters, return the number of substrings of s that contain every letter of required at least once. Substrings at different positions count separately.
Examples
Input: s = "abcabc", required = "abc"
Output: 10
Input: s = "aaacb", required = "abc"
Output: 3
Explanation: "aaacb", "aacb" and "acb".
Input: s = "abc", required = "abc"
Output: 1
Constraints
0 <= len(s) <= 10**5,1 <= len(required) <= 26- Target complexity: O(n) time; enumerating all substrings is too slow for the largest tests.
Goals
- Count, for each right edge, how many left edges give a valid window
- Track how many required letters the window currently covers