Binary search+prefix || very easy code explaination
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:\nO(26*n*logn)\n\n- Space complexity:\nO(n*26)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\nbool solve(const vector<vector<int>>& arr, int i, int mid, const vector<int>& count) {\n    for (int j = 0; j < 26; ++j) {\n        int freqInSubstring = arr[mid][j] - (i > 0 ? arr[i - 1][j] : 0);\n        if (freqInSubstring < count[j]) {\n            return false;\n        }\n    }\n    return true;\n}\n\nlong long validSubstringCount(string s1, string s2) {\n    vector<int> count(26, 0);\n    long long ans = 0;\n\n    // Frequency count for s2\n    for (char c : s2) {\n        count[c - \'a\']++;\n    }\n\n    int n = s1.size();\n    \n    // Create cumulative frequency array arr\n    vector<vector<int>> arr(n, vector<int>(26, 0));\n\n    // Initialize the frequency array\n    arr[0][s1[0] - \'a\'] = 1;\n    for (int i = 1; i < n; ++i) {\n        for (int j = 0; j < 26; ++j) {\n            arr[i][j] = arr[i - 1][j];  // Inherit the previous counts\n        }\n        arr[i][s1[i] - \'a\']++;  // Increment the count of current character\n    }\n\n    // For each starting index i, find the maximum valid substring\n    for (int i = 0; i < n; ++i) {\n        int s = i, e = n - 1;\n        int index = -1;\n\n        // Binary search to find the minimum \'mid\' where the substring s1[i..mid] is valid\n        while (e >= s) {\n            int mid = (s + e) / 2;\n            if (solve(arr, i, mid, count)) {\n                e = mid - 1;\n                index = mid;\n            } else {\n                s = mid + 1;\n            }\n        }\n\n        // If a valid substring is found, add the number of valid substrings starting from index i\n        if (index != -1) {\n            ans += (n - index);  // All substrings from index `i` to `n-1`\n        }\n    }\n\n    return ans;\n}\n};\n\n```
['C++']