Sliding Window with Example Walkthrough
Intuition\n1. Prefix and Rearrangement :\n- A prefix is the starting portion of a string. For example, for the string "abc", the prefix could be "a", "ab", or "
# Intuition\n1. **Prefix and Rearrangement :**\n- A prefix is the starting portion of a string. For example, for the string "abc", the prefix could be "a", "ab", or "abc".\n- Rearrangement means that we can rearrange the characters in a substring, but when rearranged, the beginning of the rearranged string must match word2.\n\n2. **Key Insight :**\n- The problem is about finding substrings of word1 whose characters can be rearranged in such a way that word2 becomes a prefix.\n- For example, the substring "bcca" can be rearranged into "abcc", and "abc" is a prefix of "abcc". Therefore, "bcca" is a valid substring.\n\n3. **Efficient Approach :**\n- Instead of checking all possible substrings (which would take too much time), we can use a sliding window technique to check character frequencies and determine when a valid substring is formed.\n- This way, we can avoid recalculating from scratch for every substring and just adjust the window as we process each new character.\n\n# Approach\n1. **Character Frequency Calculation :**\n- First, we calculate the frequency of each character in word2 and store it in a frequency vector v of size 26 (for the 26 lowercase letters).\n  \n2. **Sliding Window Setup :**\n- We maintain a sliding window over word1 to check its substrings.\n- The window will keep track of character frequencies in word1 using another vector cnt of size 26.\n- The sliding window will expand and shrink as needed. We will adjust the window as we move through the string word1.\n\n3. **Tracking Remaining Matches :**\n- We introduce a variable k which represents how many characters from word2 are yet to be matched within the window.\n- Initially, k = length(word2), and it decreases as we match characters of word2 inside the current window of word1.\n- When k == 0, it means the current window of word1 contains enough characters to potentially be rearranged into a valid substring that starts with word2.\n\n4. **Expanding the Window :**\n- For each character in word1, we:\na) Add the character to the current window (by updating cnt).\nb) If this character exists in word2 and is still needed in the window (i.e., cnt has fewer occurrences of this character than v), we reduce k by 1.\nc) If k == 0, we have a valid window that can potentially form a valid substring.\n\n5. **Counting Valid Substrings :**\n- Once we have a valid window (when k == 0), we count all substrings that can be formed by extending the window from the current position to the end of word1.\n- The total number of such substrings is given by len(word1) - i, where i is the current end of the window.\n\n6. **Shrinking the Window :**\n- After counting, we begin shrinking the window from the left by moving the start pointer.\n- As we remove characters from the left of the window, we update cnt and adjust k if necessary (i.e., if a character becomes unmatched).\n\n# Example Walkthrough \nLet\'s go through the example word1 = "bcca" and word2 = "abc" step by step using the code.\n\n## Initial Setup :\n After iterating over "abc", v looks like this:\n### v = [1, 1, 1, 0, 0, 0, ..., 0]\nThis indicates that word2 contains one occurrence each of the letters \'a\', \'b\', and \'c\'.\n\ncnt is initialized to track the frequency of characters in the current sliding window of word1. Initially, all elements of cnt are 0.\n\n### cnt = [0, 0, 0, ..., 0]\n### start = 0 => This represents the start of the current window.\n\n### k = 3 =>  This is the number of characters from word2 that still need to be matched.\n\n### c = 0 =>  This will store the total number of valid substrings.\n\n## Step-by-Step Walkthrough:\n\n### Iteration 1:\n**Current character :** \'b\' (at index 0)\n\n\'b\' exists in word2 (v[\'b\' - \'a\'] = 1), and its count in the window (cnt[\'b\' - \'a\'] = 0) is less than in word2. Therefore, we decrement k by 1:\nk = 2\n\n**Update cnt for \'b\' :** cnt = [0, 1, 0, ..., 0]\n\nSince k != 0, we don\'t have a valid substring yet.\n\n### Iteration 2:\n**Current character :** \'c\' (at index 1)\n\n\'c\' exists in word2 (v[\'c\' - \'a\'] = 1), and its count in the window (cnt[\'c\' - \'a\'] = 0) is less than in word2. We decrement k by 1:\nk = 1\n\n**Update cnt for \'c\' :** cnt = [0, 1, 1, ..., 0]\n\nk != 0, so still no valid substring yet.\n\n### Iteration 3:\n**Current character :** \'c\' (at index 2)\n\n\'c\' exists in word2 (v[\'c\' - \'a\'] = 1), but its count in the window (cnt[\'c\' - \'a\'] = 1) is already equal to what\u2019s required in word2. So, we don\u2019t change k.\n\n**Update cnt for \'c\' :** cnt = [0, 1, 2, ..., 0]\n\nStill, k != 0, so no valid substring yet.\n\n### Iteration 4:\n**Current character :** \'a\' (at index 3)\n\n\'a\' exists in word2 (v[\'a\' - \'a\'] = 1), and its count in the window (cnt[\'a\' - \'a\'] = 0) is less than in word2. We decrement k by 1:\nk = 0\n\n**Update cnt for \'a\' :** cnt = [1, 1, 2, ..., 0]\n\n## Now, k == 0, meaning the window from start = 0 to i = 3 forms a valid substring.\n\nWe calculate the number of valid substrings starting at start = 0 and ending at or after i = 3:\n\nThe total length of word1 is 4. Therefore, there is 4 - 3 = 1 valid substring: "bcca".\n\n**Increment c by 1 :** c = 1\n\n## Now, we shrink the window by moving start to the right and updating counts.\n\nThe leftmost character is \'b\'. Reduce the count of \'b\' in cnt:\ncnt = [1, 0, 2, ..., 0]\n\nSince we reduced the count of \'b\' below its needed count in word2, we increment k by 1:\nk = 1\n\nMove start to 1.\n\n## Final Answer:\nAfter processing all characters in word1, the total number of valid substrings is 1.\n\n# Code\n```cpp []\nlong long validSubstringCount(string s1, string s2){\n        vector<int> v(26,0);\n        for(char c : s2){\n            v[c-\'a\']++;\n        }\n\n        vector<int> cnt(26, 0);\n        int start=0, k=s2.length();\n        long long c=0;\n\n        for(int i=0;i<s1.length();i++){\n            char curr=s1[i];\n\n            if(v[curr-\'a\']>0){\n                if(cnt[curr-\'a\']<v[curr-\'a\']){\n                    k--;\n                }\n            }\n\n            cnt[curr-\'a\']++;\n\n            while(k==0){\n                c+=s1.length()-i;\n\n                char pre=s1[start];\n                cnt[pre-\'a\']--;\n\n                if(v[pre-\'a\']>0  and cnt[pre-\'a\']<v[pre-\'a\']){\n                    k++;\n                }\n\n                start++;\n            }\n        }\n\n        return c;\n    }\n```\n\n```Python []\ndef validSubstringCount(self,word1, word2) :\n    v = [0] * 26\n    for c in word2:\n        v[ord(c) - ord(\'a\')] += 1\n\n    cnt = [0] * 26\n    start = 0\n    k = len(word2)\n    count = 0\n\n    for i in range(len(word1)):\n        curr = word1[i]\n        if v[ord(curr) - ord(\'a\')] > 0:\n            if cnt[ord(curr) - ord(\'a\')] < v[ord(curr) - ord(\'a\')]:\n                k -= 1\n            \n        cnt[ord(curr) - ord(\'a\')] += 1\n\n        while k == 0:\n            count += len(word1) - i\n            pre = word1[start]\n            cnt[ord(pre) - ord(\'a\')] -= 1\n            if v[ord(pre) - ord(\'a\')] > 0 and cnt[ord(pre) - ord(\'a\')] < v[ord(pre) - ord(\'a\')]:\n                k += 1\n            start += 1\n\n        return count\n```\n\n```Java []\npublic static long validSubstringCount(String word1, String word2) {\n        int[] v = new int[26];\n        for (char c : word2.toCharArray()) {\n            v[c - \'a\']++;\n        }\n\n        int[] cnt = new int[26];\n        int start = 0;\n        int k = word2.length();\n        long count = 0;\n\n        for (int i = 0; i < word1.length(); i++) {\n            char curr = word1.charAt(i);\n            if (v[curr - \'a\'] > 0) {\n                if (cnt[curr - \'a\'] < v[curr - \'a\']) {\n                    k--;\n                }\n            }\n\n            cnt[curr - \'a\']++;\n\n            while (k == 0) {\n                count += word1.length() - i;\n                char pre = word1.charAt(start);\n                cnt[pre - \'a\']--;\n                if (v[pre - \'a\'] > 0 && cnt[pre - \'a\'] < v[pre - \'a\']) {\n                    k++;\n                }\n                start++;\n            }\n        }\n\n        return count;\n    }\n```\n\n
['Sliding Window', 'Python', 'C++', 'Java']