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 II

Number: 3572

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two strings, word1 and word2, count the number of nonempty substrings of word1 that are “valid”. A substring is considered valid if the characters in it can be rearranged so that word2 becomes its prefix. In other words, every letter in word2 must appear in the substring with at least the same frequency as in word2.

Key Insights

  • The substring is valid if it contains at least as many of each character as word2.
  • Instead of checking every substring (which is prohibitively expensive), use a sliding window approach.
  • Maintain character frequency counters over the current window and “expand” the window until the substring meets the frequency requirements dictated by word2.
  • When a minimal valid window [L, R] is found, every extension of this window (i.e. adding characters past R) is also valid.
  • Use two pointers (L and R) and update a match counter to quickly determine when a window meets all the required counts for each character in word2.

Space and Time Complexity

Time Complexity: O(n) where n is the length of word1, since each character is processed at most twice. Space Complexity: O(1) because the frequency arrays are of constant size (26 for lowercase letters) plus the required frequency array for word2 which is also fixed by the 26 letters.

Solution

To solve the problem, precompute the frequency of every character in word2. Then, use a sliding window over word1 to maintain the frequency of characters in the current window. Keep a counter (matchCount) of how many characters have reached the required frequency. For each position L from the start of word1, move the right pointer R until the window [L, R] contains every character in word2 in sufficient quantity. Once a valid window is found, any substring [L, k] with k ≥ R is valid since adding extra characters does not remove validity. Count these substrings as (n - R + 1). Before moving L to the next index, update the frequency array by removing word1[L] and, if necessary, update the match counter. This guarantees that each character is added and removed at most once, resulting in linear runtime.

Code Solutions

# Python implementation with detailed comments
def countValidSubstrings(word1: str, word2: str) -> int:
    n = len(word1)
    # Frequency requirements for each letter from word2
    required = [0] * 26
    for ch in word2:
        required[ord(ch) - ord('a')] += 1

    # Current frequency counter for the sliding window in word1
    windowCount = [0] * 26

    # Number of letters that have met the required frequency
    matchCount = 0
    # Count how many distinct letters are required
    conditionCount = sum(1 for cnt in required if cnt > 0)
    
    result = 0
    r = 0

    # Slide the left pointer of the window
    for l in range(n):
        # Extend the window while it is not valid and r is within bounds
        while r < n and matchCount < conditionCount:
            idx = ord(word1[r]) - ord('a')
            windowCount[idx] += 1
            # If adding this character reaches the required frequency for this character, increment matchCount
            if windowCount[idx] == required[idx]:
                # Only increment if the letter was required (required[idx] > 0)
                if required[idx] > 0:
                    matchCount += 1
            r += 1

        # If the window is valid, then all substrings starting at l with ending index >= r-1 are valid.
        if matchCount == conditionCount:
            result += (n - r + 1)
        
        # Before moving the left pointer, remove the influence of word1[l]
        idx = ord(word1[l]) - ord('a')
        # If removing causes the count to drop below the requirement, adjust matchCount
        if windowCount[idx] == required[idx] and required[idx] > 0:
            matchCount -= 1
        windowCount[idx] -= 1

    return result

# Example usage:
print(countValidSubstrings("bcca", "abc"))  # Output: 1
print(countValidSubstrings("abcabc", "abc"))  # Output: 10
print(countValidSubstrings("abcabc", "aaabc"))  # Output: 0
← Back to All Questions