0ms solution
IntuitionTry to figure out the relation between valid substringsApproachA substring is defined as the interval[i, j].For a valid substring[i, j],[i + 1, j]is va
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Try to figure out the relation between valid substrings

# Approach
<!-- Describe your approach to solving the problem. -->
A substring is defined as the interval `[i, j]`.

For a valid substring `[i, j]`, `[i + 1, j]` is valid if `word1[i]` is not in `word2[i]`. 

Instead of comparing charaters every iteration, just use keep a variable `c` that indicates whether there are any missing characters of `word2`. Since this is a frequent operation which saves 26 computations, the speedup is significant by dropping the constant multiplication in terms of time complexity.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n_1 + n_2)$$ 

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(1)$$ because it uses only counter variables.

# Code
```cpp []
class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        int c = 0;
        vector<int> cnt1(256, 0);
        vector<int> cnt2(256, 0);
        long long ans = 0;

        for (int i = 0; i < n2; ++i) {
            if (cnt2[word2[i]] == 0) {
                c++;
            }
            cnt2[word2[i]]++;
        }

        long long lo = 0;
        long long hi = 0;

        while (hi < n1) {
            cnt1[word1[hi]]++;
            if (cnt1[word1[hi]] == cnt2[word1[hi]]) {
                c--;
            }
            hi++;

            while (c == 0 && lo < hi) {
                ans += (n1 - hi + 1);
                cnt1[word1[lo]]--;
                if (cnt1[word1[lo]] < cnt2[word1[lo]]) {
                    c++;
                }
                lo++;
            }
        }
        return ans;
    }
};
```
['C++']