Count Beautiful Substrings I

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. Return the number of non-empty beautiful substrings in the given string s.

Key Insights

• A substring must have an equal count of vowels and consonants to be considered beautiful.
• The product of the counts of vowels and consonants must be divisible by k.
• We can use a sliding window approach to efficiently count vowels and consonants in substrings.
• A hash table can help track the counts of vowels and consonants efficiently.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem, we can iterate through all possible substrings of the input string s. For each substring, we will count the number of vowels and consonants. We will check if the counts are equal and if their product is divisible by k. A hash table can be used to store previously computed counts for efficient retrieval.

1. Initialize a counter for beautiful substrings.
2. Use nested loops to generate all substrings of s.
3. For each substring, count the vowels and consonants.
4. Check if the conditions for being beautiful are met.
5. Increment the counter for each beautiful substring found.
6. Return the counter at the end.

Code Solutions