3297. Count Substrings That Can Be Rearranged to Contain a String I

MediumHash TableStringSliding Window

Problem Description

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.

Intuition

The problem involves finding how many substrings within word1 have the capability to be rearranged in such a way that they contain word2 as a prefix. This implies that the substrings must have all characters from word2 in the correct amount.

The approach we use involves the sliding window technique. We maintain a window that shifts over word1, keeping track of the character counts in it. Let's break down the solution step by step:

Check necessary conditions: If word1 is shorter than word2, it's immediately impossible for any substrings to exist that can include all characters of word2. Hence, we can return 0.
Character frequency requirement: We create a frequency count (cnt) of characters needed from word2. This tells us how many of each character we require to have a valid prefix.
Sliding window setup: We use a sliding window (win) to count characters in the current window of word1. A variable need is used to track how many characters still need to be met according to cnt.
Expand and contract the window: As we move through each character in word1:
- Expand the window to include the current character and update the count in win.
- If a character count matches that of cnt, decrease need since one requirement is satisfied.
- Contract the window from the left to find the minimal Windows that satisfy word2. If removing the leftmost character breaks the requirement, adjust need accordingly.
Count valid substrings: Each point where need becomes zero indicates a valid condition, with all substrings ending at the current right boundary having this valid setup. These substrings are counted by the left boundary's index, l.

The answer is compiled by counting all valid substrings as determined by the moving window. This efficient approach involves O(n) time complexity due to the sliding window covering each character once or twice.

Learn more about Sliding Window patterns.

Solution Approach

Sliding Window Technique

The solution uses a sliding window method to find and count valid substrings efficiently, adhering to the requirements specified by word2. Let's delve deeper into how this algorithm functions:

Initial Setup:
- The first check is to see if word1 is shorter than word2. If true, return 0 immediately since it's never possible to form the required prefix.
- Construct a frequency count cnt for word2 using Python's Counter, which helps track how many of each character we need.
- Initialize a variable need to determine how many that still need to be satisfied, initially set to the number of unique characters found in cnt.
Sliding Window Mechanics:
- Utilize a counter win to note occurrences of characters within the current window of word1.
- Begin with a window starting from the first character, looping through word1 while extending and evaluating the window.
- For each character included, increment its count in win; if it matches the required count in cnt, decrease need because one condition has been met.
Window Adjustment and Counting:
- Once need hits zero, it indicates that the current window contains all characters necessary for rearranging into a valid prefix of word2.
- Start contracting the window from the left by incrementing l (left boundary). If you note that shrinking the window causes a count to match cnt, then increase need because the condition is no longer satisfied.
- Calculate and accumulate valid substrings count. Each valid configuration from left l to the current position contributes l valid substrings.
Final Result:
- After iterating through all characters and maintaining window dynamics, the result stored in ans is returned, representing the total count of valid substrings.

In summary, this approach ensures that each character in word1 is handled precisely in a dynamic window, leading to O(n) time complexity, which is optimal for this type of problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example with word1 = "abacb" and word2 = "abc" to illustrate the sliding window approach:

Initial Setup:
- word1: "abacb"
- word2: "abc"
- Frequency count of word2 is {'a': 1, 'b': 1, 'c': 1} using a Counter.
- need is initialized to the number of unique characters: 3.
Sliding Window Execution:
- Create win for character counts in word1, starting from an empty counter.
- Begin with pointers l = 0 and r = 0 (left and right boundary of the window).
Step-by-step window processing:
- r = 0: Include character 'a'.
  - win becomes {'a': 1}.
  - need reduces to 2 because 'a' in win meets cnt.
- r = 1: Include character 'b'.
  - win becomes {'a': 1, 'b': 1}.
  - need reduces to 1 because 'b' in win meets cnt.
- r = 2: Include character 'a'.
  - win becomes {'a': 2, 'b': 1}.
  - need remains 1 since additional 'a' does not fulfill any new need.
- r = 3: Include character 'c'.
  - win becomes {'a': 2, 'b': 1, 'c': 1}.
  - need becomes 0 as all characters are now sufficient to make a prefix.
- Valid substrings detected from position l = 0 to positions r = 2, 3.
  - Increment valid count: l = 1, 2.
- Contract Window: Start moving l to potentially find new valid substrings.
  - Increment l; l = 1. win updates to {'a': 1, 'b': 1, 'c': 1}. Still valid, need remains 0.
  - Increment valid count as l = 1 is still valid.
- r = 4: Include character 'b'.
  - win becomes {'a': 1, 'b': 2, 'c': 1}.
  - need remains 0.
- More valid substrings detected from l = 1 to l = 3.
  - Final valid counts from these configurations.
Final Result:
- The total valid substrings equate to those counted as window shifted appropriately: 3.

Using the sliding window technique efficiently tracks and counts substrings, resulting in an optimal solution.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def validSubstringCount(self, word1: str, word2: str) -> int:
5        # If the length of word1 is smaller than word2, no valid substrings can be found
6        if len(word1) < len(word2):
7            return 0
8      
9        # Create a Counter object of word2 to track the frequency of each character
10        counter_word2 = Counter(word2)
11        # 'need' keeps track of the number of unique characters still needed in the current window
12        need = len(counter_word2)
13        # Initialize variables for the answer and left pointer of window
14        answer = 0
15        left = 0
16      
17        # Counter for characters in the current window of word1
18        window_counter = Counter()
19      
20        # Iterate over each character in word1
21        for char in word1:
22            # Increase the count of the character in the current window
23            window_counter[char] += 1
24            # If the count of char in window matches the count in word2, reduce the 'need'
25            if window_counter[char] == counter_word2[char]:
26                need -= 1
27          
28            # Adjust the window when all needed characters are included
29            while need == 0:
30                # Check if reducing the count of the character at 'left' will increase 'need'
31                if window_counter[word1[left]] == counter_word2[word1[left]]:
32                    need += 1
33                # Reduce the count of the character at the left side of the window
34                window_counter[word1[left]] -= 1
35                # Move the left pointer to the right
36                left += 1
37          
38            # Add the current position of left to the answer (number of valid initial substrings)
39            answer += left
40      
41        return answer
42

1class Solution {
2    public long validSubstringCount(String word1, String word2) {
3        // If word1 is shorter than word2, there can be no valid substring
4        if (word1.length() < word2.length()) {
5            return 0;
6        }
7      
8        int[] charCountWord2 = new int[26]; // Array to track character frequency in word2
9        int uniqueCharNeeds = 0; // Counter for unique characters in word2
10      
11        // Populate the character frequency array for word2
12        for (int i = 0; i < word2.length(); ++i) {
13            if (++charCountWord2[word2.charAt(i) - 'a'] == 1) {
14                ++uniqueCharNeeds;
15            }
16        }
17      
18        long validSubstringCount = 0;
19        int[] windowCharCount = new int[26]; // Array to track character frequency in the current window of word1
20      
21        // Use a sliding window approach with two pointers l (left) and r (right)
22        for (int left = 0, right = 0; right < word1.length(); ++right) {
23            int currentChar = word1.charAt(right) - 'a';
24            // Increase count for the rightmost character in the window
25            if (++windowCharCount[currentChar] == charCountWord2[currentChar]) {
26                --uniqueCharNeeds;
27            }
28          
29            // If we have satisfied all character needs, attempt to minimize the window
30            while (uniqueCharNeeds == 0) {
31                currentChar = word1.charAt(left) - 'a';
32                // If removing the leftmost character makes the window invalid, adjust the need count
33                if (windowCharCount[currentChar] == charCountWord2[currentChar]) {
34                    ++uniqueCharNeeds;
35                }
36                --windowCharCount[currentChar];
37                ++left;
38            }
39            // Add the number of valid substrings ending at the current right character
40            validSubstringCount += left;
41        }
42      
43        return validSubstringCount;
44    }
45}
46

1class Solution {
2public:
3    long long validSubstringCount(std::string word1, std::string word2) {
4        // If word1 is shorter than word2, no valid substring is possible
5        if (word1.size() < word2.size()) {
6            return 0;
7        }
8
9        // Array to store the frequency of each character in word2
10        int requiredCharCount[26] = {};
11        // Number of different characters needed to form a valid substring
12        int uniqueNeeds = 0;
13
14        // Populate requiredCharCount based on word2
15        for (char& c : word2) {
16            if (++requiredCharCount[c - 'a'] == 1) {
17                ++uniqueNeeds;
18            }
19        }
20
21        long long result = 0;
22        int windowCharCount[26] = {}; // Array to store frequency of current window in word1
23        int leftIndex = 0; // Start of the sliding window
24      
25        // Iterate over each character of word1 with a sliding window approach
26        for (char& c : word1) {
27            int currentIndex = c - 'a';
28            // Increment the character count for the current window
29            if (++windowCharCount[currentIndex] == requiredCharCount[currentIndex]) {
30                --uniqueNeeds;
31            }
32
33            // Shrink the window from the left as long as all characters from word2 are present
34            while (uniqueNeeds == 0) {
35                currentIndex = word1[leftIndex] - 'a';
36                if (windowCharCount[currentIndex] == requiredCharCount[currentIndex]) {
37                    ++uniqueNeeds;
38                }
39                --windowCharCount[currentIndex];
40                ++leftIndex;
41            }
42
43            // Add the number of starting positions of valid substrings ending at the current character
44            result += leftIndex;
45        }
46
47        return result;
48    }
49};
50

1// Function to count valid substrings between two words
2function validSubstringCount(word1: string, word2: string): number {
3    // Initialize variable to store the count of valid substrings
4    let count = 0;
5
6    // Helper function to check if a substring of word1 exists in word2
7    function isSubstring(substr: string, mainStr: string): boolean {
8        return mainStr.includes(substr);
9    }
10
11    // Iterate through word1 to generate all possible substrings
12    for (let start = 0; start < word1.length; start++) {
13        for (let end = start + 1; end <= word1.length; end++) {
14            // Generate a substring and check if it exists in word2
15            const substring = word1.substring(start, end);
16            if (isSubstring(substring, word2)) {
17                // Increment the count if the substring is found in word2
18                count++;
19            }
20        }
21    }
22
23    // Return the total count of valid substrings
24    return count;
25}
26

Time and Space Complexity

The time complexity of the code is O(n + m), where n is the length of word1 and m is the length of word2. This complexity arises from the need to iterate over each character in both strings: first to populate the Counter for word2 and then to iterate through each character in word1 to manage the sliding window.

The space complexity is O(|Σ|), where Σ refers to the character set used within the strings. Since we are considering lowercase letters, the space is effectively constant (O(1)), as the Counter objects cnt and win are limited by the size of this character set.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know