Watch 7 video solutions for Count Substrings That Can Be Rearranged to Contain a String II, a hard level problem involving Hash Table, String, Sliding Window. This walkthrough by codingMohan has 923 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |