Count Substrings That Can Be Rearranged to Contain a String II

Problem Description

You are given two strings word1 and word2. A string x is called valid if x can be rearranged to have word2 as a prefix. Return the total number of valid non-empty substrings of word1.

Key Insights

• A substring is valid if it contains at least the same number of each character present in word2.
• We can use a sliding window approach to maintain a count of characters in the current substring of word1.
• When the window size is at least the length of word2, we can check if the substring can be rearranged to contain word2 as a prefix.
• Efficiently check if the current character counts meet the requirements specified by word2.

Space and Time Complexity

Time Complexity: O(n), where n is the length of word1.
Space Complexity: O(1), since the character count array has a fixed size of 26 for lowercase English letters.

Solution

To solve this problem, we can use a sliding window approach along with a hash table (or a fixed-size array) to count characters. Here's how it works:

1. Count the characters in word2 using a frequency map.
2. Initialize a sliding window over word1 and maintain a count of characters in the current window.
3. Expand the window by moving the right pointer and include more characters from word1 while checking if the window can be rearranged to match word2.
4. When the window size is at least the length of word2, check if the character counts in the window satisfy the counts required by word2.
5. If valid, count the substring and move the left pointer to shrink the window.

Code Solutions