Even Vowel and Consonant Pieces

Medium

You get a string text of lowercase English letters and a positive integer divisor. The vowels are a, e, i, o and u; every other letter is a consonant. Call a non-empty substring (a contiguous piece of the string) **balanced** if it has as many vowels as consonants and the number of vowels times the number of consonants is divisible by divisor. Return how many balanced substrings there are. Pieces with the same letters at different positions count separately.

Example 1

text="moon", divisor=1 → 3

"mo" (1 vowel, 1 consonant), "on" (1 and 1) and the whole "moon" (2 and 2) all qualify. A divisor of 1 divides any product.

Example 2

text="moon", divisor=4 → 1

For "mo" and "on" the product is 1·1 = 1, not divisible by 4. Only "moon" remains: 2·2 = 4.

Example 3

text="xyz", divisor=1 → 0

Constraints

1 ≤ len(text) ≤ 2000
1 ≤ divisor ≤ 1000
text contains only lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table Math String Enumeration Number Theory Prefix Sum

Similar problems

Balanced Stretches of a String Hard Pieces With Matching Ends Medium Pieces With a Fixed Zero-to-One Ratio Medium Primes Along Grid Rays Medium Pair GCDs by Sorted Position Hard

Input

text="moon", divisor=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.