[Python3] Hash Table + Sliding Window - Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\nThe provided Python c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nThe provided Python code defines a function validSubstringCount that calculates the number of valid substrings in word1 that can be formed by concatenating substrings from word2. A valid substring is one where the frequency of each character in the substring is less than or equal to its frequency in word2.\n\n**1. Initialization:**\n\n- `cnt` is a counter to keep track of the frequency of characters in `word2`.\n- `match` is initialized to the number of unique characters in `word2`.\n- `res` is used to store the count of valid substrings.\n- `j` is used to keep track of the starting index of the current substring.\n\n**2. Iteration:**\n\n- The loop iterates over each character `ch` in `word1` at index `i`.\n- The frequency of `ch` in `cnt` is decremented.\n- If the frequency of `ch` becomes 0, `match` is decremented to indicate that a new unique character has been encountered.\n- While `match` is 0, it means that the current substring is valid.\n    - The loop continues to increment `j` until a character is found that has a frequency greater than 0 in `cnt`.\n    - The frequency of the character at index `j` is incremented in `cnt`.\n    - `match` is incremented if the frequency becomes 0.\n- `res` is incremented to count the valid substring.\n\n**3. Return Value:**\n\n- The final value of `res` is returned, which represents the total number of valid substrings.\n\nIn summary, the code iterates through `word1`, maintaining a sliding window of valid substrings. The sliding window expands as long as the frequency of characters in the current substring does not exceed their frequency in `word2`. The number of valid substrings is counted based on the length of the sliding window.\n\n# Complexity\n- Time complexity: $$O(W1 + W2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(26)$$ ~ $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def validSubstringCount(self, word1: str, word2: str) -> int:\n        cnt = collections.Counter(word2)\n        match, res, j = len(cnt), 0, 0\n        for i, ch in enumerate(word1):\n            cnt[ch] -= 1\n            match -= cnt[ch] == 0\n            while match == 0:\n                match += cnt[word1[j]] == 0\n                cnt[word1[j]] += 1\n                j += 1\n            res += j\n        return res\n```
['Hash Table', 'Sliding Window', 'Python3']