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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Substrings That Can Be Rearranged to Contain a String I

Difficulty: Medium

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 non-empty substrings of word1.

Key Insights

  • A substring is valid if it contains at least the same number of each character in word2.
  • We can count the occurrences of each character in word2 using a hash table.
  • As we explore substrings of word1, we can use a sliding window approach to maintain the counts of characters.
  • If a substring meets the character requirements for word2, it is counted as valid.

Space and Time Complexity

Time Complexity: O(n * m) where n is the length of word1 and m is the length of word2.
Space Complexity: O(1) since the character set is fixed (only lowercase English letters).

Solution

We can utilize a sliding window approach along with a hash table to track character counts. The algorithm involves iterating through word1 and maintaining a frequency count of characters in the current substring. For each character added, we check if the substring can be rearranged to start with word2 by comparing counts with the target character counts derived from word2.

Code Solutions

def count_valid_substrings(word1, word2):
    from collections import Counter
    
    word2_count = Counter(word2)
    word2_length = len(word2)
    valid_count = 0
    
    for start in range(len(word1)):
        current_count = Counter()
        for end in range(start, len(word1)):
            current_count[word1[end]] += 1
            
            if all(current_count[char] >= word2_count[char] for char in word2_count):
                valid_count += 1
                
    return valid_count
← Back to All Questions