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 substrings of word1.
Note that the memory limits in this problem are smaller than usual, so you must implement a solution with a linear runtime complexity.
Example 1:
Input: word1 = "bcca", word2 = "abc"
Output: 1
Explanation:
The only valid substring is "bcca" which can be rearranged to "abcc" having "abc" as a prefix.
Example 2:
Input: word1 = "abcabc", word2 = "abc"
Output: 10
Explanation:
All the substrings except substrings of size 1 and size 2 are valid.
Example 3:
Input: word1 = "abcabc", word2 = "aaabc"
Output: 0
Constraints:
1 <= word1.length <= 1061 <= word2.length <= 104word1 and word2 consist only of lowercase English letters.This approach utilizes a sliding window to manage the substrings of word1 and checks their character counts against the count of characters in word2. By keeping track of character counts inside the window and comparing with the required counts in word2, we can efficiently identify valid substrings.
The solution initiates character counts for word2 and uses them as a baseline. We then use a sliding window with a length equal to word2. As we expand the window by adding a character and contracting it by removing a character when it exceeds the length, we maintain the character count of the window. Whenever the character counts in the current window match or exceed the counts in word2, we have a valid substring.
C++
Time Complexity: O(n), where n is the length of word1, due to the single pass required to maintain and check character counts.
Space Complexity: O(1), as we use a fixed space count dictionary which does not scale with input size.
This approach uses two pointers to denote the boundaries of a window on word1 and adjusts dynamically while maintaining valid sets of character counts. We increment the right pointer to expand the window and adjust the left pointer to contract it, ensuring it matches or exceeds word2 prefix requirement.
The solution employs two HashMaps to track counts within a sliding window on word1 and to track the necessary counts from word2. It allows dynamic adjustment using left and right pointers to ensure the window maintains the required conditions.
JavaScript
Time Complexity: O(n), where n is the length of word1, facilitated by the two-pointer technique.
Space Complexity: O(1), considering fixed space is used for character counts similar to the Python solution.
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Count | Time Complexity: O(n), where n is the length of word1, due to the single pass required to maintain and check character counts. |
| Two-pointer Technique | Time Complexity: O(n), where n is the length of word1, facilitated by the two-pointer technique. |
Count of Substrings Containing Every Vowel and K Consonants II - Leetcode 3306 - Python • NeetCodeIO • 14,848 views views
Watch 9 more video solutions →Practice Count Substrings That Can Be Rearranged to Contain a String II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor