We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Substrings That Can Be Rearranged to Contain a String I

Number: 3573

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two strings word1 and word2, count the total number of non-empty substrings of word1 that are valid. A substring is considered valid if, after any rearrangement, word2 appears as its prefix. In other words, the substring must contain at least the frequency of each character present in word2.

Key Insights

  • A substring can be rearranged arbitrarily, so the order does not matter. We only need to ensure that the substring has at least as many of each character as word2.
  • Create a frequency count for word2 (required counts) and use a sliding window on word1 to check if a current window meets or exceeds these counts.
  • Once a valid window starting at index i is found (with a minimal ending index j), every substring starting from i and ending at any index beyond j will also be valid.
  • Use two pointers (sliding window) to efficiently count the number of valid substrings and avoid O(n^2) enumeration.

Space and Time Complexity

Time Complexity: O(n * k) where n is the length of word1 and k is the size of the alphabet (typically 26).
Space Complexity: O(1) since the frequency arrays have a fixed size independent of input length.

Solution

We use a two-pointer (sliding window) approach with frequency arrays. First, compute the frequency of each character in word2 which serves as the requirement. Then, iterate over word1 with a left pointer (i) and expand a right pointer (j) until the window [i, j] meets or exceeds the required frequency for every character in word2. When a valid window is found, every substring that extends this window (i.e. [i, j], [i, j+1], …, [i, n-1]) will be valid, and we add (n - j) to our result. Before moving i to the next index, remove its effect from the window count and continue.

Key Data Structures:

  • Two fixed-size integer arrays (or dictionaries) to store character frequencies for the current window and for word2.
  • Two pointers to mark the boundaries of the current substring window.

The main trick is recognizing that once the window is valid, extending its right boundary keeps it valid. This allows efficient counting without re-checking all substrings one by one.

Code Solutions

Below are code solutions in multiple languages with line-by-line comments.

# Python implementation of the solution

def count_valid_substrings(word1: str, word2: str) -> int:
    # Frequency requirements for characters in word2
    req = [0] * 26
    for ch in word2:
        req[ord(ch) - ord('a')] += 1

    n = len(word1)
    left = 0
    right = 0
    count_valid = 0
    current = [0] * 26

    # Function to check if current window satisfies the req 
    def is_valid():
        for i in range(26):
            if current[i] < req[i]:
                return False
        return True

    # Use sliding window approach to find minimal right index for each left index
    while left < n:
        # Expand right until the window is valid or we run off the end
        while right < n and not is_valid():
            current[ord(word1[right]) - ord('a')] += 1
            right += 1
        # If the window is valid, all substrings starting at left with end index >= right-1 are valid
        if is_valid():
            count_valid += (n - right + 1)
        # Shrink the window from the left before moving left pointer further
        current[ord(word1[left]) - ord('a')] -= 1
        left += 1

    return count_valid

# Example usage:
print(count_valid_substrings("bcca", "abc"))  # Expected output: 1
← Back to All Questions