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 Beautiful Substrings II

Difficulty: Hard

Problem Description

You are given a string s and a positive integer k. A string is beautiful if the number of vowels equals the number of consonants, and the product of vowels and consonants is divisible by k. Your task is to return the number of non-empty beautiful substrings in the given string s.

Key Insights

  • A substring is contiguous, so we can use a sliding window approach.
  • We need to maintain a count of vowels and consonants as we iterate through the string.
  • The conditions for a beautiful substring require checking both the equality of vowels and consonants and the divisibility of their product by k.
  • A hash map can be useful to keep track of the counts of (vowels - consonants) and their occurrences to efficiently find substrings that meet the conditions.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(n), for storing the counts in a hash map.

Solution

To solve the problem, we can utilize a two-pointer (or sliding window) technique along with a hash map to count the occurrences of (vowels - consonants). As we iterate through the string, we update our counts for vowels and consonants. For each substring, we check if the conditions for being beautiful are met, and if so, we increment our result count accordingly.

Code Solutions

def count_beautiful_substrings(s, k):
    vowels = set('aeiou')
    count = {}
    count[(0, 0)] = 1  # base case: one way to have (0 vowels, 0 consonants)
    vowel_count = 0
    consonant_count = 0
    result = 0

    for char in s:
        if char in vowels:
            vowel_count += 1
        else:
            consonant_count += 1
        
        # Check if the number of vowels and consonants are equal
        if vowel_count == consonant_count:
            if (vowel_count * consonant_count) % k == 0:
                result += count.get((vowel_count, consonant_count), 0)
        
        # Update the map with the current counts
        count[(vowel_count, consonant_count)] = count.get((vowel_count, consonant_count), 0) + 1
    
    return result
← Back to All Questions