using prefix which has space complexity  O[N][26]
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution\n{\npublic:\n  long long validSubstringCount(string word1, string word2)\n  {\n    int n = word1.size();\n    int m = word2.size();\n    vector<int> freq(26, 0);\n    for (int i = 0; i < m; i++)\n    {\n      freq[word2[i] - \'a\']++;\n    }\n    vector<vector<int>> v(26, vector<int>(n + 1, 0));\n\n    for (int i = 0; i < n; i++)\n    {\n      int x = word1[i] - \'a\';\n      for (int j = 0; j < 26; j++)\n      {\n        v[j][i + 1] = v[j][i];\n      }\n      v[x][i + 1] = v[x][i] + 1;\n    }\n    long long count = 0;\n    for (int i = m; i <= n; i++)\n    {\n      int cnt = 0;\n      int mini = 1e8;\n      for (int j = 0; j < 26; j++)\n      {\n        if (v[j][i] >= freq[j])\n          cnt++;\n      }\n      if (cnt == 26)\n      {\n        for (int j = 0; j < 26; j++)\n        {\n\n          int r = v[j][i];\n          int l = r - freq[j];\n          if (r != 0)\n          {\n            int ind = upper_bound(v[j].begin(), v[j].end(), l) - v[j].begin();\n            mini = min(mini, ind);\n          }\n        }\n      }\n\n     if(mini != 1e8) count += mini;\n    }\n\n    return count;\n  }\n};\n\n\n```
['C++']