Sliding Window || C++ 🔍🧩
Intuition\n Describe your first thoughts on how to solve this problem. \nTo find valid substrings of s that can be rearranged to have p as a prefix, we need to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find valid substrings of $$s$$ that can be rearranged to have $$p$$ as a prefix, we need to ensure that each substring contains at least the same frequency of characters as in $$p$$. This can be efficiently tracked using a sliding window and character counts.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Character Count for p:** Use an unordered map $$mpP$$ to store frequencies of characters in $$p$$\n2. **Sliding Window:** Employ two pointers ($$i$$ and $$j$$) to maintain a window in $$s$$: \n- Expand $$j$$ and update a second map $$mpS$$ for the current window.\n- When a character from $$p$$ is fully matched in $$mpS$$, increment $$cnt$$.\n\n3. **Count Valid Substrings:** If $$cnt$$ equals the unique character count from $$p$$, add $$(n - j)$$ to the result, as all remaining characters form valid substrings. Then, increment $$i$$ to narrow the window, adjusting $$mpS$$ accordingly.\n4. **Repeat Until All Characters Are Processed:** Continue until $$j$$ has processed all characters in $$s$$.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(1)$$\n# Code\n```cpp []\n\nclass Solution {\npublic:\n    using ll = long long;\n    long long validSubstringCount(string s, string p) {\n\n        int n = s.size(), m = p.size();\n        if (m > n) return 0;\n\n        unordered_map<char, int> mpP, mpS;\n        for (char c : p) \n            mpP[c]++;\n\n        ll ans = 0;\n        int uniqCnt = mpP.size();\n        int cnt = 0;\n\n        int i = 0;\n        for (int j = 0; j < n; j++) {\n            char c = s[j];\n            mpS[c]++;\n            if (mpP.count(c) && mpS[c] == mpP[c]) {\n                cnt++;\n            }\n\n            while (cnt == uniqCnt) {\n                ans += (n - j);\n\n                char leftCh = s[i];\n                mpS[leftCh]--;\n                if (mpP.count(leftCh) && mpS[leftCh] < mpP[leftChar]) {\n                    cnt--;\n                }\n                i++;\n            }\n        }\n        return ans;\n    }\n};\n\n```
['Ordered Map', 'Sliding Window', 'C++']