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.Problem Overview: You are given two strings. Count how many substrings of the main string can be rearranged so that the target string appears inside it. A substring is valid if its character frequencies contain at least the same counts as the target string.
Approach 1: Sliding Window with Frequency Count (O(n) time, O(1) space)
This approach uses a sliding window combined with a character frequency counter. First compute the frequency of each character in the target string. Expand the right pointer across the main string while maintaining a window frequency array. Once the window satisfies all required character counts, every extension of this window to the right also remains valid. Shrink the left pointer to find the minimal valid window while accumulating the number of valid substrings. Since each pointer moves at most n times, the algorithm runs in O(n) time with O(1) space (fixed alphabet).
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The two-pointer technique is a slightly different framing of the same idea. Maintain two indices representing the current substring boundaries and track character counts using an array or hash table. Move the right pointer to include characters until the substring contains all characters required by the target string. Once valid, move the left pointer forward while counting all substrings that still satisfy the requirement. The key insight: if a window starting at l and ending at r is valid, then any window ending after r is also valid. This lets you add multiple substrings in constant time.
Both methods rely on maintaining character frequencies and verifying whether the window covers the target string requirements. Using fixed-size arrays for lowercase characters avoids expensive map operations and keeps the algorithm linear. The logic is commonly implemented in languages like Python, C++, Java, and JavaScript using simple arrays indexed by character codes.
Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see that you recognize the substring counting pattern where a valid window implies multiple valid extensions. Demonstrating the frequency check and efficient window contraction shows strong understanding of string processing and sliding window optimization.
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.
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.
Java
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.
The problem is essentially to find how many substrings in word1 contain all the characters in word2. We can use a sliding window to handle this.
First, if the length of word1 is less than the length of word2, then it is impossible for word1 to contain all the characters of word2, so we directly return 0.
Next, we use a hash table or an array of length 26 called cnt to count the occurrences of characters in word2. Then, we use need to record how many more characters are needed to meet the condition, initialized to the length of cnt.
We then use a sliding window win to record the occurrences of characters in the current window. We use ans to record the number of substrings that meet the condition, and l to record the left boundary of the window.
We traverse each character in word1. For the current character c, we add it to win. If the value of win[c] equals cnt[c], it means the current window already contains one of the characters in word2, so we decrement need by one. If need equals 0, it means the current window contains all the characters in word2. We need to shrink the left boundary of the window until need is greater than 0. Specifically, if win[word1[l]] equals cnt[word1[l]], it means the current window contains one of the characters in word2. After shrinking the left boundary, it no longer meets the condition, so we increment need by one and decrement win[word1[l]] by one. Then, we increment l by one. At this point, the window is [l, r]. For any 0 leq l' < l, [l', r] are substrings that meet the condition, and there are l such substrings, which we add to the answer.
After traversing all characters in word1, we get the answer.
The time complexity is O(n + m), where n and m are the lengths of word1 and word2, respectively. The space complexity is O(|\Sigma|), where \Sigma is the character set. Here, it is the set of lowercase letters, so the space complexity is constant.
Python
Java
C++
Go
TypeScript
| 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. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Frequency Count | O(n) | O(1) | Best general solution for substring counting with character constraints |
| Two-Pointer Technique | O(n) | O(1) | Useful when implementing minimal valid window logic and counting extensions |
3298. Count Substrings That Can Be Rearranged to Contain a String II | Weekly Leetcode 416 • codingMohan • 923 views views
Watch 6 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