问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
You are given a string s and a positive integer k.
Let vowels and consonants be the number of vowels and consonants in a string.
A string is beautiful if:

vowels == consonants.
(vowels * consonants) % k == 0, in other terms the multiplication of vowels and consonants is divisible by k.

Return the number of non-empty beautiful substrings in the given string s.
A substring is a contiguous sequence of characters in a string.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.
Consonant letters in English are every letter except vowels.

Example 1:

Input: s = "baeyh", k = 2
Output: 2
Explanation: There are 2 beautiful substrings in the given string.
- Substring "baeyh", vowels = 2 (["a",e"]), consonants = 2 (["y","h"]).
You can see that string "aeyh" is beautiful as vowels == consonants and vowels * consonants % k == 0.
- Substring "baeyh", vowels = 2 (["a",e"]), consonants = 2 (["b","y"]).
You can see that string "baey" 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.

Example 2:

Input: s = "abba", k = 1
Output: 3
Explanation: There are 3 beautiful substrings in the given string.
- Substring "abba", vowels = 1 (["a"]), consonants = 1 (["b"]).
- Substring "abba", vowels = 1 (["a"]), consonants = 1 (["b"]).
- Substring "abba", vowels = 2 (["a","a"]), consonants = 2 (["b","b"]).
It can be shown that there are only 3 beautiful substrings in the given string.

Example 3:

Input: s = "bcdf", k = 1
Output: 0
Explanation: There are no beautiful substrings in the given string.


Constraints:

1 <= s.length <= 1000
1 <= k <= 1000
s consists of only English lowercase letters.

### Format: You will use the following starter code to write the solution to the problem and enclose your code within delimiters.
```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:

```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = 'aeiou'
count = 0
n = len(s)

for i in range(n):
v_count = 0
c_count = 0
for j in range(i, n):
if s[j] in vowels:
v_count += 1
else:
c_count += 1
if v_count == c_count and (v_count * c_count) % k == 0:
count += 1
return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
deepseek-r1

```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = {'a', 'e', 'i', 'o', 'u'}
n = len(s)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + (1 if s[i] in vowels else 0)
count = 0
for i in range(n):
max_l = n - i
for l in range(2, max_l + 1, 2):
j = i + l - 1
current_vowels = prefix[j+1] - prefix[i]
m = l // 2
if current_vowels == m and (m * m) % k == 0:
count += 1
return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
gpto1 ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels_set = {'a', 'e', 'i', 'o', 'u'}
n = len(s)
count = 0

for i in range(n):
vowels = 0
consonants = 0
for j in range(i, n):
if s[j] in vowels_set:
vowels += 1
else:
consonants += 1
if vowels == consonants and vowels > 0:
if (vowels * consonants) % k == 0:
count += 1
return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
gpt-4o-2024-08-06 ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels_set = {'a', 'e', 'i', 'o', 'u'}
n = len(s)
beautiful_count = 0

# Iterate over all possible substrings
for start in range(n):
vowels = 0
consonants = 0
for end in range(start, n):
if s[end] in vowels_set:
vowels += 1
else:
consonants += 1

# Check if the current substring is beautiful
if vowels == consonants and (vowels * consonants) % k == 0:
beautiful_count += 1

return beautiful_count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
def is_vowel(c):
return c in 'aeiou'

count = 0
n = len(s)

for i in range(n):
for j in range(i + 1, n + 1):
substr = s[i:j]
vowels = consonants = 0
for char in substr:
if is_vowel(char):
vowels += 1
else:
consonants += 1
if vowels == consonants and (vowels * consonants) % k == 0:
count += 1

return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
n = len(s)
res = 0
for i in range(n):
vowel_count = 0
consonant_count = 0
for j in range(i, n):
if s[j] in vowels:
vowel_count += 1
else:
consonant_count += 1
if vowel_count == consonant_count and vowel_count * consonant_count % k == 0 and vowel_count != 0:
res += 1
return res
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
res = 0
for i in range(len(s)):
v, c = 0, 0
for j in range(i, len(s)):
if s[j] in vowels:
v += 1
else:
c += 1
if v == c and v * c % k == 0:
res += 1
return res
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
Qwen2-72B-Instruct ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
n = len(s)
beautiful_count = 0

for i in range(n):
v, c = 0, 0
for j in range(i, n):
if s[j] in vowels:
v += 1
else:
c += 1
if v == c and (v * c) % k == 0:
beautiful_count += 1

return beautiful_count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
baichuan4 ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
count = 0
vowel_count = 0
consonant_count = 0
last_vowel_count = 0
last_consonant_count = 0

for char in s:
if char in vowels:
vowel_count += 1
last_consonant_count = consonant_count
consonant_count = 0
else:
consonant_count += 1
last_vowel_count = vowel_count
vowel_count = 0

if vowel_count == consonant_count and (vowel_count * consonant_count) % k == 0:
count += 1

if last_vowel_count == last_consonant_count and (last_vowel_count * last_consonant_count) % k == 0:
count += 1

return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
doubao ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = 'aeiou'
count = 0
for i in range(len(s)):
vowel_count = 0
consonant_count = 0
for j in range(i, len(s)):
if s[j] in vowels:
vowel_count += 1
else:
consonant_count += 1
if vowel_count == consonant_count and vowel_count * consonant_count % k == 0 and vowel_count > 0 and consonant_count > 0:
count += 1
return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
gpto1 ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels_set = {'a', 'e', 'i', 'o', 'u'}
n = len(s)
count = 0

for i in range(n):
vowels = 0
consonants = 0
for j in range(i, n):
if s[j] in vowels_set:
vowels += 1
else:
consonants += 1
if vowels == consonants and vowels > 0:
if (vowels * consonants) % k == 0:
count += 1
return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
kimi ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
count = 0
v_count = 0
c_count = 0
prefix_sum = {(0, 0): 1}

for i, char in enumerate(s):
if char in vowels:
v_count += 1
else:
c_count += 1

if v_count == c_count and v_count * c_count % k == 0:
count += 1

for j in range(i + 1, len(s)):
if s[j] in vowels:
v_count += 1
else:
c_count += 1

if v_count == c_count and v_count * c_count % k == 0:
count += 1

if (v_count - 1, c_count) in prefix_sum:
count += prefix_sum[v_count - 1, c_count]

if (v_count, c_count) not in prefix_sum:
prefix_sum[v_count, c_count] = 0

prefix_sum[v_count, c_count] += 1

if s[j] in vowels:
v_count -= 1
else:
c_count -= 1

return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
minimax ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
beautiful_count = 0
vowel_count = 0
consonant_count = 0
prefix_vowel_count = [0] * (len(s) + 1)
prefix_consonant_count = [0] * (len(s) + 1)

for i in range(1, len(s) + 1):
if s[i - 1] in vowels:
vowel_count += 1
else:
consonant_count += 1

prefix_vowel_count[i] = vowel_count
prefix_consonant_count[i] = consonant_count

for j in range(i):
if prefix_vowel_count[i] - prefix_vowel_count[j] == prefix_consonant_count[i] - prefix_consonant_count[j]:
if (prefix_vowel_count[i] - prefix_vowel_count[j]) * (prefix_consonant_count[i] - prefix_consonant_count[j]) % k == 0:
beautiful_count += 1

return beautiful_count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
wenxinyiyan ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
consonants = set('bcdfghjklmnpqrstvwxyz')
n = len(s)
count = 0

# Helper function to check if a substring is beautiful
def is_beautiful(substring):
vowel_count = sum(1 for c in substring if c in vowels)
consonant_count = sum(1 for c in substring if c in consonants)
return vowel_count == consonant_count and (vowel_count * consonant_count) % k == 0

# Check all possible substrings
for i in range(n):
for j in range(i+1, n+1):
substring = s[i:j]
if is_beautiful(substring):
count += 1

return count

# Optimized solution using prefix sums
class SolutionOptimized:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
n = len(s)
count = 0
prefix_sums = [[0, 0] for _ in range(n + 1)] # [vowels, consonants]

# Compute prefix sums
for i in range(1, n + 1):
prefix_sums[i][0] = prefix_sums[i-1][0] + (1 if s[i-1] in vowels else 0)
prefix_sums[i][1] = i - prefix_sums[i][0] # Total characters - vowels = consonants

# Check all possible substrings using prefix sums
for i in range(n):
for j in range(i+1, n+1):
vowels_count = prefix_sums[j][0] - prefix_sums[i][0]
consonants_count = prefix_sums[j][1] - prefix_sums[i][1]
if vowels_count == consonants_count and (vowels_count * consonants_count) % k == 0:
count += 1

return count

# Further optimized solution using hash table to store prefix sum frequencies
class SolutionFurtherOptimized:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
n = len(s)
count = 0
prefix_sum = 0
freq = {0: 1} # Initialize with prefix sum 0 having frequency 1

# Compute prefix sums and update frequencies
for i in range(n):
if s[i] in vowels:
prefix_sum += 1
else:
prefix_sum -= 1

# If the current prefix sum modulo 2k is seen before,
# it means there is a substring with equal number of vowels and consonants
# and their product is divisible by k.
# We add the frequency of the previously seen prefix sum to the count.
count += freq.get((prefix_sum + k) % (2 * k), 0)

# Update the frequency of the current prefix sum
freq[prefix_sum % (2 * k)] = freq.get(prefix_sum % (2 * k), 0) + 1

return count

# Note: The further optimized solution uses a hash table to store the frequencies
# of prefix sums modulo 2k. This allows us to efficiently check for substrings
# with equal number of vowels and consonants, and their product divisible by k,
# without explicitly checking all possible substrings.
```
Note: The provided solutions include progressively optimized versions. The first solution is a brute-force approach that checks all possible substrings. The second solution uses prefix sums to optimize the computation of vowel and consonant counts. The third solution further optimizes by using a hash table to store prefix sum frequencies, reducing the time complexity.

However, for the given problem constraints, the second optimized solution (using prefix sums) should suffice and provide efficient results. The third solution (using hash table) is included for completeness and to demonstrate an advanced optimization technique.		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
zhipu ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = set('aeiou')
n = len(s)
count = 0

for i in range(n):
vowel_count = 0
consonant_count = 0

for j in range(i, n):
if s[j] in vowels:
vowel_count += 1
else:
consonant_count += 1

if vowel_count == consonant_count and (vowel_count * consonant_count) % k == 0:
count += 1

return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]
deepseek-v3 ```python
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
vowels = {'a', 'e', 'i', 'o', 'u'}
n = len(s)
count = 0
for i in range(n):
v = 0
c = 0
for j in range(i, n):
if s[j] in vowels:
v += 1
else:
c += 1
if v == c and (v * c) % k == 0:
count += 1
return count
```		 [{"input": "\"baeyh\"\n2", "output": "2", "testtype": "functional"}, {"input": "\"abba\"\n1", "output": "3", "testtype": "functional"}, {"input": "\"bcdf\"\n1", "output": "0", "testtype": "functional"}]