Easy solution using map and vector, works for part 2 also
Count Substrings That Can Be Rearranged to Contain a String I\n\n## Intuition\nTo solve the problem of counting how many substrings of word1 can be rearranged t
# Count Substrings That Can Be Rearranged to Contain a String I\n\n## Intuition\nTo solve the problem of counting how many substrings of `word1` can be rearranged to have `word2` as a prefix, we recognize that we need to track the frequency of characters. A substring can be rearranged to contain `word2` if it has at least the same count of each character that `word2` has. This suggests a method involving maintaining character counts and checking them as we slide through `word1`.\n\n## Approach\n1. **Frequency Maps**: Use a frequency map for `word2` to count the characters.\n2. **Sliding Window**: Traverse `word1` using a sliding window approach:\n   - For each character in `word1`, decrease the count in a frequency array for characters seen so far.\n   - When all characters from `word2` are matched, count all valid substrings that can be formed from the current position to the end of `word1`.\n   - Adjust the left pointer of the window to explore other potential valid substrings.\n\n## Complexity\n- Time complexity: $$O(n)$$, where `n` is the length of `word1`. The algorithm primarily consists of a single pass through `word1`, with constant time checks for character counts.\n  \n- Space complexity: $$O(1)$$ for the frequency array since the size is fixed at 26 (for the lowercase English alphabet).\n\n## Code\n```cpp\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n        \n        int n1 = word1.size();\n        int n2 = word2.size();\n\n        // Array x to track frequency of characters in word2\n        vector<int> x(26, 0);\n        \n        // If word2 is longer than word1, no valid substrings can exist\n        if (n2 > n1) return 0;\n\n        // Map f stores the frequency of characters in word2\n        unordered_map<char, int> f;\n\n        // Populate the map f and array x with frequencies of each character in word2\n        for (char c : word2) {\n            f[c]++;\n            x[c - \'a\']++;\n        }\n\n        // i is the left pointer, t is the count of valid substrings\n        int i = 0;\n        long long t = 0;\n\n        // j is the right pointer that iterates over word1\n        for (int j = 0; j < n1; j++) {\n            char c = word1[j];\n\n            // If current character is not in word2, skip it\n            if (!f.count(c))\n                continue;\n\n            // Decrease the frequency count of the current character\n            x[c - \'a\']--;\n\n            // Check if all characters from word2 are present in the window\n            if (*max_element(x.begin(), x.end()) == 0) {\n                // Expand the left pointer i to find all valid substrings\n                while (i < n1) {\n                    // Add the number of valid substrings from this point\n                    t += n1 - j;\n\n                    // If word1[i] is not in word2, move the left pointer\n                    if (!f.count(word1[i])) {\n                        i++;\n                        continue;\n                    }\n\n                    // Restore the frequency count of the character at word1[i]\n                    x[word1[i] - \'a\']++;\n\n                    // If all characters are still covered, move the left pointer\n                    if (x[word1[i] - \'a\'] <= 0) {\n                        i++;\n                    } else {\n                        // Otherwise, break the loop as the window is no longer valid\n                        i++;\n                        break;\n                    }\n                }\n            }\n        }\n\n        // Return the total number of valid substrings found\n        return t;\n    }\n};\n\n
['Sliding Window', 'C++']