Algorithms
Hard
2949
3208
Count Beautiful Substrings II
count-beautiful-substrings-ii
"""
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 <= 5 * 104
1 <= k <= 1000
s consists of only English lowercase letters.
"""
class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        
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 <= 5 * 104
1 <= k <= 1000
s consists of only English lowercase letters.


Please complete the code below to solve above prblem:
```python
class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        
```

my_solution = Solution()

test_input = { "s": "baeyh", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "abba", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "bcdf", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "ihroyeeb", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "uzuxpzou", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "ouuoeqd", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "eeebjoxxujuaeoqibd", "k": 8 }
assert my_solution.beautifulSubstrings(**test_input) == 4

test_input = { "s": "ilougekqlovegioemdvu", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 21

test_input = { "s": "tqaewreikaztwpfwnef", "k": 8 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "oykiuhsafgfjumnzb", "k": 7 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "ifvsa", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "svzauyuevujektj", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "urahjig", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "ime", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "oacghieut", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "aoluu", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "ioaoiciiuoziout", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 5

test_input = { "s": "ouafupsuhid", "k": 6 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "ox", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "tlaiwoauazutusiaaui", "k": 10 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "caepeym", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "apyxvceue", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "imkqbb", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "caaz", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "pyicoy", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 6

test_input = { "s": "uopmyrsntjhiroikup", "k": 8 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "aujfxqxcj", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "eeizejuoxeumz", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 6

test_input = { "s": "uuouuaifnboeiulttio", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 10

test_input = { "s": "woozzxd", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "pulorolqcvhafexui", "k": 9 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "hmuaewojioizoguvoaje", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 4

test_input = { "s": "b", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "aiejouohnqnketinvat", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 6

test_input = { "s": "mjiogpri", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "movbyaeouil", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "puureouausxmitvav", "k": 6 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "op", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "iuhoezpooxcohtlapolo", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 39

test_input = { "s": "cioi", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "pueutaoyaxk", "k": 6 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "iiuresacruaaan", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "agntyaazvpejidwaph", "k": 8 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "wiybolyniexiibou", "k": 6 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "coiyakadxi", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 8

test_input = { "s": "oraajoeruiakixj", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "jeayap", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 7

test_input = { "s": "iu", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "awozoy", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "fheabmlsyeeeuoeogyz", "k": 9 }
assert my_solution.beautifulSubstrings(**test_input) == 5

test_input = { "s": "eaizneuxi", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 10

test_input = { "s": "uurqufaucsuoqljh", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 14

test_input = { "s": "jrtept", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "olgioxooiejooosaed", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "uizoy", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "lswabfiujjhexzos", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 5

test_input = { "s": "iuu", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "qeaxut", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 7

test_input = { "s": "aojiau", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "oaiaaaargkonlcsoaygf", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "zoowrawkm", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "uqiwuoevkfhkkua", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 6

test_input = { "s": "kavuaaeodvaxicm", "k": 6 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "qpxeceq", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 6

test_input = { "s": "iaabaofuodcbek", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "eel", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "ikeuhe", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 5

test_input = { "s": "lueikvo", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "oauau", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "qzoieeotieeakqraeao", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 4

test_input = { "s": "ehaascocsdmgekni", "k": 9 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "euqeklniykiji", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "vaeiiioidiioxhduu", "k": 7 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "aa", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "chaua", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "edfrglfr", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "dqbe", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "ghooirorxge", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 6

test_input = { "s": "fodartekaonq", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 9

test_input = { "s": "feeanzkjpfehzeuni", "k": 6 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "ignoouesduu", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 6

test_input = { "s": "yif", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "gondfjaeeuhbuuasgip", "k": 10 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "djooomsffoonelyeode", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 14

test_input = { "s": "pgaimei", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 2

test_input = { "s": "naipqentonee", "k": 4 }
assert my_solution.beautifulSubstrings(**test_input) == 8

test_input = { "s": "bouov", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "lcuhoypz", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "g", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "qc", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "mhznea", "k": 2 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "uxvjixdujgyfauo", "k": 8 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "iyjkuox", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "xbjfoayfpafatnuyord", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "nvoede", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 1

test_input = { "s": "usnuaxpaktrweatruu", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "euojmsora", "k": 1 }
assert my_solution.beautifulSubstrings(**test_input) == 10

test_input = { "s": "iapgoi", "k": 3 }
assert my_solution.beautifulSubstrings(**test_input) == 0

test_input = { "s": "uafuimcpxyeoixgbyeio", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 3

test_input = { "s": "weuaatpu", "k": 5 }
assert my_solution.beautifulSubstrings(**test_input) == 0