Facebook Pixel

3298. Count Substrings That Can Be Rearranged to Contain a String II

HardHash TableStringSliding Window
Leetcode Link

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. Note that the memory limits in this problem are smaller than usual, so you must implement a solution with a linear runtime complexity.

Intuition

To solve the problem, we need to determine how many substrings of word1 can be rearranged to contain word2 as a prefix. We can efficiently solve this by using a sliding window approach:

  1. Counting Characters: First, count the occurrences of characters in word2 as this is the condition that needs to be met.

  2. Sliding Window: Traverse through word1 maintaining a window that counts characters within it. This window represents a substring of word1.

  3. Track Remaining Needs: Use a counter need to track how many more characters are needed to form a valid substring.

  4. Adjust Window: As you expand the window by including each character of word1, check if adding this character satisfies one of the needed character counts. If it does, decrease the need.

  5. Form Valid Substrings: When the need becomes zero, it means the window currently contains all needed characters at least once. From this position, shrink the left boundary of the window until the need becomes greater than zero again, marking the transition back to an invalid state.

  6. Count Valid Substrings: For each position where need is zero and as you slide the window by moving the left boundary, note how many valid substrings can be formed by incrementing a count of such substrings.

This solution efficiently counts valid substrings by leveraging the sliding window to minimize redundant checks, maintaining linear time complexity as required by the problem constraints.

Learn more about Sliding Window patterns.

Solution Approach

Sliding Window Method

The goal is to identify substrings within word1 that can be rearranged to contain word2 as a prefix. To fulfill this, we utilize the sliding window technique which efficiently tracks and updates the count of characters within a moving window of word1.

  1. Initial Validation: Immediately return 0 if word1 is shorter than word2, as word1 cannot include all the characters necessary.

  2. Character Counting:

    • Use a Counter from the collections module to count the occurrences of each character in word2. This will help us determine the needed characters for any substring to be valid.
    • need is initialized to the number of distinct characters in word2.

  3. Sliding Window Setup:

    • Initialize two pointers, l for the left boundary of the window and iterate through word1 with c as the current character.
    • Use win, another Counter, to maintain the character count within the current window of word1.

  4. Expanding and Shrinking the Window:

    • For each character c in word1, increment the count in win. If this count matches the count in cnt (indicating a needed character), decrement need.
    • When need becomes zero (all needed characters are present), shrink the window from the left:
      • If removing word1[l] from the window influences a needed character's count, increment need, indicating the window no longer fully satisfies the conditions after contraction.
      • Adjust the count in win[ word1[l] ] and shift the left pointer l.

  5. Count Valid Substrings: Each time need equals zero, it indicates a valid range from the current left marker l to the current position. The number of valid substrings is incremented by l.

  6. Result Calculation: Continue the process until every character of word1 has been evaluated, and return the total number of valid substrings stored in ans.

This methodology ensures a linear time complexity since each character in word1 is processed a fixed number of times, aligning with the memory constraints specified.

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 a simple example to demonstrate the solution using the sliding window approach.

Suppose word1 = "abacb" and word2 = "abc".

  1. Character Counting:

    • Count the occurrences in word2:
      • cnt = {'a': 1, 'b': 1, 'c': 1}
    • Initialize need = 3, which is the number of distinct characters in word2.

  2. Sliding Window Setup:

    • Initialize two pointers: l = 0 (left boundary) and win = {} (to keep track of characters in the current window).

  3. Expanding the Window:

    • As we iterate over word1:

      • r = 0, c = 'a':

        • Increment win['a']: win = {'a': 1}
        • Since win['a'] meets cnt['a'], decrement need: need = 2

      • r = 1, c = 'b':

        • Increment win['b']: win = {'a': 1, 'b': 1}
        • win['b'] meets cnt['b'], decrement need: need = 1

      • r = 2, c = 'a':

        • Increment win['a']: win = {'a': 2, 'b': 1}
        • need remains 1 as cnt['a'] is already satisfied.

      • r = 3, c = 'c':

        • Increment win['c']: win = {'a': 2, 'b': 1, 'c': 1}
        • win['c'] meets cnt['c'], decrement need: need = 0

  4. Valid Substring Detection:

    • With need = 0, we have a valid substring word1[l:r+1] = "abac".
    • Increment result: ans += l + 1 = 1

  5. Shrink the Window:

    • Move left boundary and adjust:

      • l = 1:

        • Decrement win['a']: win = {'a': 1, 'b': 1, 'c': 1}
        • need remains 0, so add another valid substring word1[l:r+1] = "bac".
        • ans += l + 1 = 3

      • l = 2:

        • Decrement win['b']: win = {'a': 1, 'b': 0, 'c': 1}
        • need goes to 1, no more valid substring.

  6. Continue the Process:

    • r = 4, c = 'b':

      • Increment win['b']: win = {'a': 1, 'b': 1, 'c': 1}
      • need becomes 0, valid substring word1[l:r+1] = "acb".
      • ans += l + 1 = 4

    • Adjust left boundary:

      • l = 3:
        • Decrement win['a']: win = {'a': 0, 'b': 1, 'c': 1}
        • No more valid substrings can be made, as need becomes 1.

  7. Result:

    • The total count of valid substrings is ans = 4.

With this approach, each character of word1 is processed efficiently, ensuring the solution respects linear runtime constraints.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def validSubstringCount(self, word1: str, word2: str) -> int:
5        # Return 0 if word1 is shorter than word2
6        if len(word1) < len(word2):
7            return 0
8      
9        # Count characters in word2
10        count_word2 = Counter(word2)
11        required_characters = len(count_word2)
12      
13        # Initialize variables
14        result = left_pointer = 0
15        window_counter = Counter()
16      
17        # Iterate over each character in word1
18        for char in word1:
19            window_counter[char] += 1
20          
21            # Check if current character count matches the one in word2
22            if window_counter[char] == count_word2[char]:
23                required_characters -= 1
24          
25            # When all required characters are matched
26            while required_characters == 0:
27                # If the left character of the window's count exactly matches word2
28                if window_counter[word1[left_pointer]] == count_word2[word1[left_pointer]]:
29                    required_characters += 1
30                # Decrease the count of the left character in the window
31                window_counter[word1[left_pointer]] -= 1
32                left_pointer += 1
33          
34            # Add the position of the left pointer to result
35            result += left_pointer
36      
37        return result
38
1class Solution {
2    public long validSubstringCount(String word1, String word2) {
3        // If word1 is shorter than word2, no valid substring is possible
4        if (word1.length() < word2.length()) {
5            return 0;
6        }
7      
8        // Array to store the count of each character in word2
9        int[] targetCount = new int[26];
10        int distinctCharCountNeeded = 0;
11      
12        // Populate the targetCount array based on characters in word2
13        for (int i = 0; i < word2.length(); ++i) {
14            if (++targetCount[word2.charAt(i) - 'a'] == 1) {
15                // Increment the number of distinct characters needed
16                ++distinctCharCountNeeded;
17            }
18        }
19      
20        long substringsCount = 0;
21        int[] windowCount = new int[26];
22      
23        // Sliding window approach to find valid substrings
24        for (int left = 0, right = 0; right < word1.length(); ++right) {
25            int rightCharIndex = word1.charAt(right) - 'a';
26            if (++windowCount[rightCharIndex] == targetCount[rightCharIndex]) {
27                // Character matches, decrease the need
28                --distinctCharCountNeeded;
29            }
30          
31            // Try to shrink the window from the left if all needed characters are in the window
32            while (distinctCharCountNeeded == 0) {
33                int leftCharIndex = word1.charAt(left) - 'a';
34                if (windowCount[leftCharIndex] == targetCount[leftCharIndex]) {
35                    // Character match will break, need to increment back the need
36                    ++distinctCharCountNeeded;
37                }
38                // Remove the left character from the window
39                --windowCount[leftCharIndex];
40                // Move the left edge of the window forward
41                ++left;
42            }
43          
44            // Add the number of valid starting points for substrings ending at `right`
45            substringsCount += left;
46        }
47      
48        return substringsCount;
49    }
50}
51
1class Solution {
2public:
3    // Function to calculate the number of valid substrings
4    long long validSubstringCount(std::string word1, std::string word2) {
5        // If word1 is shorter than word2, no valid substring exists
6        if (word1.size() < word2.size()) {
7            return 0;
8        }
9
10        // Frequency count arrays for each alphabet character
11        int countWord2[26] = {};  // To count the frequency of characters in word2
12        int neededChars = 0;      // To track the number of unique characters needed from word2
13
14        // Calculating frequency of characters in word2
15        for (char& c : word2) {
16            if (++countWord2[c - 'a'] == 1) {
17                ++neededChars;      // Increment neededChars for each unique character in word2
18            }
19        }
20
21        long long result = 0;      // To store the result for the number of valid substrings
22        int window[26] = {};       // Frequency count array for the current window in word1
23        int leftIndex = 0;         // Left boundary of the window in word1
24
25        // Iterating through each character in word1
26        for (char& c : word1) {
27            int currentIndex = c - 'a';   // Get the index for the character
28            if (++window[currentIndex] == countWord2[currentIndex]) {
29                --neededChars;            // If frequency matches, reduce the needed character count
30            }
31
32            // Adapting the window when all needed characters are included
33            while (neededChars == 0) {
34                currentIndex = word1[leftIndex] - 'a';
35                if (window[currentIndex] == countWord2[currentIndex]) {
36                    ++neededChars;        // If frequency is exact, increase need
37                }
38                --window[currentIndex];   // Shrink the window from the left
39                ++leftIndex;              // Move the left boundary to the right
40            }
41            result += leftIndex;          // Add possible starting positions for valid substrings
42        }
43
44        return result;                     // Return the total number of valid substrings
45    }
46};
47
1function validSubstringCount(word1: string, word2: string): number {
2    // If word1 is shorter than word2, it's impossible for word1 to have any valid substrings.
3    if (word1.length < word2.length) {
4        return 0;
5    }
6
7    // Initialize an array to count the characters in word2.
8    const cnt: number[] = Array(26).fill(0);
9    let neededCharacters: number = 0;
10
11    // Populate cnt array with frequencies of each character in word2.
12    for (const char of word2) {
13        // Increment the count of the character by its ASCII index minus offset for 'a'.
14        if (++cnt[char.charCodeAt(0) - 97] === 1) {
15            ++neededCharacters;
16        }
17    }
18
19    // Initialize an array to manage the window of characters in word1.
20    const windowCounts: number[] = Array(26).fill(0);
21    let answer: number = 0;
22    let leftPointer: number = 0;
23
24    // Iterate through all characters in word1.
25    for (const char of word1) {
26        const index = char.charCodeAt(0) - 97;
27
28        // Increment count in the current window
29        if (++windowCounts[index] === cnt[index]) {
30            --neededCharacters;
31        }
32
33        // Adjust the window to maintain the condition neededCharacters == 0.
34        while (neededCharacters === 0) {
35            const leftIndex = word1[leftPointer].charCodeAt(0) - 97;
36
37            // Only shrink the window if the shrink reduces a matching count.
38            if (windowCounts[leftIndex] === cnt[leftIndex]) {
39                ++neededCharacters;
40            }
41
42            // Decrease the count of the character at leftPointer and move the pointer.
43            --windowCounts[leftIndex];
44            ++leftPointer;
45        }
46
47        // Add up valid positions for the left pointers.
48        answer += leftPointer;
49    }
50
51    return answer;
52}
53

Time and Space Complexity

The time complexity is O(n + m), where n and m are the lengths of word1 and word2, respectively. This is because the code iterates over word1 once and uses a sliding window approach without nested loops.

The space complexity is O(|Σ|), where Σ is the character set. Since the code uses counters for characters in word2 and the sliding window in word1, and the set of lowercase letters is constant, the space complexity is constant.

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

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Recommended Readings

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More