Count Substrings That Can Be Rearranged to Contain a String I - Solution & Explanation
Problem Statement
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.
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 <= 1051 <= word2.length <= 104word1andword2consist only of lowercase English letters.
Approach Overview
Problem Overview: You are given a string and another target string. The task is to count how many substrings can be rearranged so that the substring contains all characters of the target string. Since rearrangement is allowed, only the character frequencies matter, not their order.
Approach 1: Sliding Window with Character Count (O(n) time, O(1) space)
This approach uses the classic sliding window technique combined with a character frequency map. First compute the required frequency of each character from the target string. Expand the right pointer across the main string while updating counts in the window. When the window has at least the required frequency for every character, the substring can be rearranged to contain the target.
Once a valid window is found, every extension of that window to the right is also valid. If the current right index is r, then all substrings ending from r to n-1 work, so you add n - r to the answer. Then shrink the window from the left to find the next minimal valid window. Frequency checks are constant time using an array or hash table. The full scan runs in O(n) time with O(1) space since the alphabet size is fixed.
Approach 2: Prefix Sum with Character Frequency (O(26 · n log n) time, O(26 · n) space)
This method precomputes prefix frequency arrays for each character in the string using a string preprocessing technique. With prefix sums, you can quickly compute the frequency of any character inside a substring [l, r] in constant time. For each starting index l, search for the smallest r where the substring contains all required frequencies of the target string.
Once such an r is found, every larger ending index also forms a valid substring. Add n - r to the result and move to the next starting index. The frequency check uses prefix differences, and finding the minimal valid r can be done with binary search or incremental scanning. This approach is easier to reason about when you already have prefix frequency infrastructure but uses more memory.
Recommended for interviews: Sliding window with character counts is the expected solution. It runs in O(n) time, uses constant space, and demonstrates strong understanding of frequency tracking and window contraction. The prefix sum method is conceptually clean but heavier in both memory and implementation.
Approach 1: Sliding Window with Character Count
This approach uses a sliding window to iterate over all possible substrings of word1. By maintaining character counts for substrings and word2, we determine if a substring can be rearranged to start with word2 as a prefix.
This Python solution uses a sliding window and a dictionary (Counter) to keep track of character frequencies. It adjusts the window size while ensuring all necessary characters from word2 are covered by the substring, incrementing the valid substring count when conditions meet.
Code
Python
JavaScript
Complexity
The time complexity is O(n) where n is the length of word1, as each character is added and removed at most twice from the sliding window. The space complexity is O(1) as the size of the dictionary is bounded by the character set.
Approach 2: Prefix Sum with Character Frequency
This approach involves utilizing prefix sums to accumulate character frequencies across word1. By comparing these accumulations with the necessary frequencies from word2, we can efficiently find valid rearrangements for substrings.
The Java solution employs a prefix sum array to track character frequencies as we traverse word1. It ensures that every substring window is checked against the character requirements from word2 with minimal recalibration of counts.
Complexity
The solution shows O(n) time complexity since each character in word1 is involved in prefix updates a fixed number of times. The space complexity is O(1), reflecting the fixed-size character frequency array.
Approach 3: Sliding Window
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Character Count | The time complexity is O(n) where n is the length of |
| Prefix Sum with Character Frequency | The solution shows O(n) time complexity since each character in |
| Sliding Window | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Character Count | O(n) | O(1) | Best general solution when scanning substrings with frequency constraints |
| Prefix Sum with Character Frequency | O(26 · n log n) | O(26 · n) | Useful when prefix frequency arrays are already available or substring queries are frequent |
Video Solution
3297. Count Substrings That Can Be Rearranged to Contain a String I | Weekly Leetcode 416 • codingMohan • 1,934 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Count Substrings That Can Be Rearranged to Contain a String I easy or hard?
Count Substrings That Can Be Rearranged to Contain a String I Python/Java solution
How to solve Count Substrings That Can Be Rearranged to Contain a String I in O(n)?
What is the best approach for Count Substrings That Can Be Rearranged to Contain a String I?
Is Count Substrings That Can Be Rearranged to Contain a String I asked at Google/Amazon/Meta?
What data structure is used in Count Substrings That Can Be Rearranged to Contain a String I?
What is the time complexity of Count Substrings That Can Be Rearranged to Contain a String I?
Ready to solve this problem?
Practice Count Substrings That Can Be Rearranged to Contain a String I with our built-in code editor and test cases.
Practice on FleetCode