Binary Search || prefix sum arrays || count valid substrings || C++.
IntuitionThe problem requires counting substrings of word1 that contain all characters of word2 at least as many times as they appear in word2. To efficiently f
# Intuition
The problem requires counting substrings of word1 that contain all characters of word2 at least as many times as they appear in word2. To efficiently find such substrings, we use prefix frequency arrays and binary search. By precomputing character frequencies in word1 using a prefix sum approach, we can quickly check if a given substring satisfies the frequency requirements. Binary search helps efficiently determine the smallest valid right endpoint for each left endpoint, reducing the time complexity significantly compared to a brute-force approach.

# Approach
1. Precompute Character Frequencies:
- We maintain a prefix array where `prefix[i][ch]` stores the number of times character `ch` appears in the prefix of word1 up to index i.
- This allows quick frequency queries for any substring `[l,r]` using the formula:
`count of ch in [l,r]=prefix[r+1][ch]−prefix[l][ch]`
2. Binary Search for the Smallest Valid `r`:
- For each starting index l, we perform binary search on r (right endpoint) to find the smallest `r` such that the substring `[l,r]` contains all characters of word2 in the required count.
- The function `isGood(l, r)` checks if the substring `[l,r]` satisfies the condition using prefix sums.
- If `isGood(l, mid)` returns true, we reduce `high (high = mid - 1)`, otherwise, we increase `low (low = mid + 1)`.
- The smallest valid r found is used to count the number of valid substrings starting at l.
3. Counting Valid Substrings:
- If the smallest valid `r` for `l` is found, all substrings starting at l and ending from `r to n-1` are valid.
- The count for `l is (n - r)`, which is accumulated in `ans`.
- Finally, `ans` is returned as the total valid substring count.
This approach significantly reduces the time complexity compared to brute-force methods.

# Complexity
- Time complexity:
O(NlogN)

- Space complexity:
O(26 × (N+1)) ≈ O(N).

# Code
```cpp []
class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        int n = word1.size();

        vector<int> cnt(26,0);
        for(auto it:word2)
        cnt[it-'a']++;

        vector<vector<int>> prefix(n+1,vector<int>(26,0));

        for(int i=1;i<=n;i++)
        {
            int currch = word1[i-1]-'a';
            prefix[i] = prefix[i-1];
            prefix[i][currch]++;
        }

        long long ans=0;
        for(int l=0;l<n;l++)
        {
            int r = isGoodForLeftmostR(l,n,prefix,cnt);
            ans+=(n-r)*1LL;
        }
        return ans;
    }
    int isGoodForLeftmostR(int r, int n, vector<vector<int>>& prefix, vector<int>& cnt)
    {
        int low = r,high = n-1;
        while(low<=high)
        {
            int mid = (low+high)/2;
            if(isGood(r, mid, prefix, cnt))
            high = mid-1;
            else
            low = mid+1;
        }
        return low;
    }
    bool isGood(int l, int r, vector<vector<int>>& prefix, vector<int>& cnt)
    {
        if(r+1>prefix.size())
        return false;
        for(int i=0;i<26;i++)
        {
            if(prefix[r+1][i] - prefix[l][i] < cnt[i])
            return false;
        }
        return true;
    }
};
```
['C++']