<p>You are given a string <code>s</code> and a positive integer <code>k</code>.</p>

<p>Let <code>vowels</code> and <code>consonants</code> be the number of vowels and consonants in a string.</p>

<p>A string is <strong>beautiful</strong> if:</p>

<ul>
	<li><code>vowels == consonants</code>.</li>
	<li><code>(vowels * consonants) % k == 0</code>, in other terms the multiplication of <code>vowels</code> and <code>consonants</code> is divisible by <code>k</code>.</li>
</ul>

<p>Return <em>the number of <strong>non-empty beautiful substrings</strong> in the given string</em> <code>s</code>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters in a string.</p>

<p><strong>Vowel letters</strong> in English are <code>&#39;a&#39;</code>, <code>&#39;e&#39;</code>, <code>&#39;i&#39;</code>, <code>&#39;o&#39;</code>, and <code>&#39;u&#39;</code>.</p>

<p><strong>Consonant letters</strong> in English are every letter except vowels.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;baeyh&quot;, k = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 2 beautiful substrings in the given string.
- Substring &quot;b<u>aeyh</u>&quot;, vowels = 2 ([&quot;a&quot;,e&quot;]), consonants = 2 ([&quot;y&quot;,&quot;h&quot;]).
You can see that string &quot;aeyh&quot; is beautiful as vowels == consonants and vowels * consonants % k == 0.
- Substring &quot;<u>baey</u>h&quot;, vowels = 2 ([&quot;a&quot;,e&quot;]), consonants = 2 ([&quot;b&quot;,&quot;y&quot;]). 
You can see that string &quot;baey&quot; is beautiful as vowels == consonants and vowels * consonants % k == 0.
It can be shown that there are only 2 beautiful substrings in the given string.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abba&quot;, k = 1
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 beautiful substrings in the given string.
- Substring &quot;<u>ab</u>ba&quot;, vowels = 1 ([&quot;a&quot;]), consonants = 1 ([&quot;b&quot;]). 
- Substring &quot;ab<u>ba</u>&quot;, vowels = 1 ([&quot;a&quot;]), consonants = 1 ([&quot;b&quot;]).
- Substring &quot;<u>abba</u>&quot;, vowels = 2 ([&quot;a&quot;,&quot;a&quot;]), consonants = 2 ([&quot;b&quot;,&quot;b&quot;]).
It can be shown that there are only 3 beautiful substrings in the given string.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bcdf&quot;, k = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no beautiful substrings in the given string.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>s</code> consists of only English lowercase letters.</li>
</ul>

# I don't understand what is happening - revisit when you have time
# Data Structures and Algorithm Used: Hash Map (Counter), Single Pass with Prefix Calculation

# Intuition:
# - We need to efficiently count substrings where the number of vowels equals the number of consonants and the product is divisible by k.
# - Using a single pass through the string, we can maintain a running difference between the count of vowels and consonants.
# - By leveraging the properties of prefix sums and a hash map, we can efficiently count the valid substrings.

# Detailed Intuition:
# - Calculate a suitable value X such that X * X % k == 0.
# - Append a character to the string to simplify boundary conditions.
# - Use a hash map to store the count of prefix differences (count of vowels - count of consonants).
# - For each character in the string, update the count and check how many times the current prefix has occurred before with the same difference.

# Pseudocode:
# 1. Initialize X such that X * X % k == 0.
# 2. Append an extra character to the string.
# 3. Initialize the count difference and a hash map.
# 4. Iterate through the string:
#    a. Update the key based on the current difference and position.
#    b. Add to the result if the key exists in the hash map.
#    c. Update the hash map with the current key.
#    d. Adjust the count based on whether the character is a vowel or consonant.
# 5. Return the result.

# Example:
# s = "aeiou", k = 1
# X is calculated to satisfy X * X % k == 0.
# We then iterate through each character, updating the hash map and counting beautiful substrings.

from collections import Counter

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        # Calculate X such that X * X % k == 0
        multiplier = 1
        while multiplier * multiplier % k != 0:
            multiplier += 1
        
        # Append an extra character to handle boundary conditions
        s += 'x'
        
        # Initialize variables
        string_length = len(s)
        beautiful_substrings_count = 0
        vowel_consonant_balance = 0
        prefix_counter = Counter()

        # Single loop to count beautiful substrings
        for index in range(string_length):
            # Create the key based on the current count and position modulo 2 * multiplier
            key = (vowel_consonant_balance, index % (2 * multiplier))
            
            # Add to the result the count of previous occurrences of this key
            beautiful_substrings_count += prefix_counter[key]
            
            # Update the hash map with the current key
            prefix_counter[key] += 1
            
            # Adjust the balance: increment for vowels, decrement for consonants
            if s[index] in "aeiou":
                vowel_consonant_balance += 1
            else:
                vowel_consonant_balance -= 1
        
        return beautiful_substrings_count  # Return the number of beautiful substrings

# Time Complexity: O(n) where n is the length of the string.
# Space Complexity: O(n) due to the use of a hash map (Counter).


# Brute force 
# Data Structures and Algorithm Used: Sliding Window, Counting

# Intuition:
# - We need to find all substrings where the number of vowels equals the number of consonants and their product is divisible by k.
# - A brute-force approach would involve checking all possible substrings, but we can optimize this with a sliding window.

# Detailed Intuition:
# - Use a sliding window to examine all possible substrings.
# - For each window, maintain counts of vowels and consonants.
# - Check if the substring meets the conditions of being "beautiful".
# - Count and return the number of beautiful substrings.

# Pseudocode:
# 1. Initialize a counter for beautiful substrings.
# 2. Iterate through each possible starting index of the substring.
# 3. For each starting index, expand the window to include all possible ending indices.
# 4. Count vowels and consonants in the current window.
# 5. If the number of vowels equals the number of consonants and their product is divisible by k, increment the counter.
# 6. Return the count of beautiful substrings.

# Example:
# s = "aeiou", k = 1
# - Substring "ae": 1 vowel, 1 consonant, product = 1, divisible by 1 -> beautiful
# - Substring "aei": 2 vowels, 1 consonant -> not beautiful

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        def is_vowel(c):
            return c in {'a', 'e', 'i', 'o', 'u'}
        
        n = len(s)
        beautiful_count = 0
        
        # Iterate through all possible starting points of substrings
        for start in range(n):
            vowels, consonants = 0, 0
            
            # Expand the window from 'start' to 'end'
            for end in range(start, n):
                if is_vowel(s[end]):
                    vowels += 1
                else:
                    consonants += 1
                
                # Check the conditions for a beautiful substring
                if vowels == consonants and (vowels * consonants) % k == 0:
                    beautiful_count += 1
        
        return beautiful_count  # Return the count of beautiful substrings

# Time Complexity: O(n^2) where n is the length of the string.
# Space Complexity: O(1) as we are only using a few extra variables.

1264