#3297

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count Substrings That Can Be Rearranged to Contain a String I

Count the number of valid substrings in word1 that can be rearranged to contain word2 as a prefix.

Problem Statement

You are given two strings word1 and word2. A valid substring of word1 can be rearranged to contain word2 as a prefix. Your task is to return the total number of such valid substrings in word1.

To solve the problem efficiently, you will need to utilize a sliding window approach. Update the window state by tracking the frequency of characters as you move through word1, and compare it to the frequency of characters in word2 to identify valid substrings.

Examples

Example 1

Input: word1 = "bcca", word2 = "abc"

Output: 1

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

All the substrings except substrings of size 1 and size 2 are valid.

Example 3

Input: word1 = "abcabc", word2 = "aaabc"

Output: 0

Example details omitted.

Constraints

1 <= word1.length <= 105
1 <= word2.length <= 104
word1 and word2 consist only of lowercase English letters.

Solution Approach

Sliding Window with Frequency Count

Use a sliding window of length equal to word2. As the window slides through word1, maintain a frequency count of the characters in the window. Compare this count to the character frequency of word2 to check if the window can be rearranged to contain word2 as a prefix.

Efficient Character Comparison

Instead of comparing the full frequency counts for every substring, efficiently update the frequency count by adding the new character and removing the old one as the window moves. This ensures that you can check validity in constant time for each slide.

Optimizing with Hash Table

Store the frequency of characters in word2 in a hash table. Then, as you slide the window across word1, maintain a similar table for the window's characters. This allows for efficient comparisons between the two tables.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sliding window approach and the frequency comparison. The space complexity is O(26) since only lowercase English letters are involved, making the space used by the hash table constant.

What Interviewers Usually Probe

Look for understanding of sliding window technique.
Evaluate the candidate's ability to optimize space and time complexity.
Test if the candidate can handle edge cases where word1 is smaller than word2 or has mismatched character frequencies.

Common Pitfalls or Variants

Common pitfalls

Not properly updating the frequency count as the window slides.
Forgetting to handle cases where word2 is longer than word1.
Incorrectly comparing the frequency tables, which might lead to false positives for valid substrings.

Follow-up variants

What if word2 is empty? How would you handle that?
How can you modify the approach if word1 and word2 can contain uppercase letters?
How would the solution change if there were constraints on the number of distinct characters in word1?

FAQ

How can I use a sliding window to solve "Count Substrings That Can Be Rearranged to Contain a String I"?

By maintaining a sliding window of the same length as word2 and updating the character frequency as it moves through word1, you can efficiently determine if a substring can be rearranged to contain word2.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the length of word1, since each character is processed once as the window slides across the string.

What should I do if word2 is longer than word1?

If word2 is longer than word1, no valid substrings can exist, so you can immediately return 0.

How do I optimize the space complexity for this problem?

The space complexity can be reduced by using a fixed-size hash table (of size 26 for lowercase English letters) to store character frequencies, making it constant space O(1).

Can the sliding window approach work for other types of substring problems?

Yes, the sliding window technique is versatile and can be used for many substring-related problems, especially when looking for substrings that meet specific conditions.

terminal

Solution

Solution 1: Sliding Window

The problem is essentially to find how many substrings in $\textit{word1}$ contain all the characters in $\textit{word2}$. We can use a sliding window to handle this.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        if len(word1) < len(word2):
            return 0
        cnt = Counter(word2)
        need = len(cnt)
        ans = l = 0
        win = Counter()
        for c in word1:
            win[c] += 1
            if win[c] == cnt[c]:
                need -= 1
            while need == 0:
                if win[word1[l]] == cnt[word1[l]]:
                    need += 1
                win[word1[l]] -= 1
                l += 1
            ans += l
        return ans

Continue Practicing

#3298 count substrings that can be rearranged to contain a string ii #3305 count of substrings containing every vowel and k consonants i #3306 count of substrings containing every vowel and k consonants ii