Question
Equal Power Vowel Substrings
You are given a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression consisting of lowercase English letters.
Consider the vowels KaTeX can only parse string typed expression. Your task is to count the number of substrings such that:
-
Each vowel appears the same number of times in the substring.
-
This common number of occurrences is a power of 2 (i.e., KaTeX can only parse string typed expression).
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting of lowercase English letters.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting of lowercase English letters.
Output
Print a single integer — the number of non-empty substrings where the occurrences of all vowels are equal and that number is a power of 2.
Example
Input
7
aeioubc
Output
3
Explanation
Valid substrings:
KaTeX can only parse string typed expression
KaTeX can only parse string typed expression
KaTeX can only parse string typed expression
Each of these substrings contains exactly one occurrence of every vowel KaTeX can only parse string typed expression.
The occurrence count is KaTeX can only parse string typed expression, which is a power of KaTeX can only parse string typed expression.
Total = KaTeX can only parse string typed expression valid substrings.
7
aeioubc
Output
3
Explanation
Valid substrings:
KaTeX can only parse string typed expression
KaTeX can only parse string typed expression
KaTeX can only parse string typed expression
Each of these substrings contains exactly one occurrence of every vowel KaTeX can only parse string typed expression.
The occurrence count is KaTeX can only parse string typed expression, which is a power of KaTeX can only parse string typed expression.
Total = KaTeX can only parse string typed expression valid substrings.