LeetCode Solutions Blog

Count Beautiful Substrings I

Number: 3210

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a string s and a positive integer k, count the number of non-empty substrings for which the number of vowels equals the number of consonants and the product (vowels * consonants) is divisible by k. Vowels are "a", "e", "i", "o", "u", and all other letters are considered consonants.

Key Insights

Only substrings of even length can have an equal number of vowels and consonants.
A brute force approach using two nested loops is acceptable given the maximum string length of 1000.
Using prefix sum arrays for vowels and consonants can optimize the count retrieval for each substring.
Checking the condition (vowels * consonants) % k == 0 must be done after confirming the counts are equal.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the string, due to the nested iteration over all substrings. Space Complexity: O(n), for storing the prefix sum arrays of vowels and consonants.

Solution

We solve the problem by iterating over all possible substrings while maintaining counts of vowels and consonants. One efficient method is to precompute two prefix sum arrays: one for vowels and one for consonants. For any substring from index i to j, the number of vowels is computed as vowels[j] - vowels[i] and similarly for consonants. We then verify if the counts are equal and if their product is divisible by k.

If the string length is small (n ≤ 1000), iterating over all possible substrings (i.e., O(n^2)) is feasible.

Code Solutions

# Python solution with line-by-line comments

def count_beautiful_substrings(s: str, k: int) -> int:
    n = len(s)
    # Define set of vowels for quick lookup
    vowels_set = {'a', 'e', 'i', 'o', 'u'}
    
    # Precompute prefix counts for vowels and consonants.
    # prefix_vowels[i] will store the number of vowels in s[0:i]
    # prefix_consonants[i] will store the number of consonants in s[0:i]
    prefix_vowels = [0] * (n + 1)
    prefix_consonants = [0] * (n + 1)
    
    for i in range(n):
        # Check if the current character is a vowel
        if s[i] in vowels_set:
            prefix_vowels[i+1] = prefix_vowels[i] + 1
            prefix_consonants[i+1] = prefix_consonants[i]
        else:
            prefix_vowels[i+1] = prefix_vowels[i]
            prefix_consonants[i+1] = prefix_consonants[i] + 1
    
    beautiful_count = 0
    # Iterate over all possible substrings
    for i in range(n):
        for j in range(i + 1, n + 1):
            # Count vowels and consonants in substring s[i:j]
            vowels_count = prefix_vowels[j] - prefix_vowels[i]
            consonants_count = prefix_consonants[j] - prefix_consonants[i]
            # Check if the substring is balanced and the product is divisible by k
            if vowels_count == consonants_count and vowels_count * consonants_count % k == 0:
                beautiful_count += 1
    
    return beautiful_count

# Example usage:
s = "baeyh"
k = 2
print(count_beautiful_substrings(s, k))  # Expected output: 2