Count Beautiful Substrings II

Count Beautiful Substrings II

What is this problem about?

The Count Beautiful Substrings II interview question is a "Hard" extension of the beautiful substrings problem. You need to count substrings where the number of vowels equals the number of consonants, and their product is divisible by k. With string lengths up to 10^5, an O(N^2) solution will time out. You must find an O(N) or O(N log N) approach.

Why is this asked in interviews?

Amazon uses this String interview pattern to test your ability to optimize complex counting problems using mathematical insights and frequency maps. It evaluates if you can simplify a multi-variable condition (vowels == consonants and product % k == 0) into a single coordinate in a Hash Map. It's a true test of algorithmic maturity.

Algorithmic pattern used

The problem uses Prefix Sums and Hash Maps.

1. Let v be number of vowels and c be number of consonants. Condition v == c implies v - c = 0.
2. Let x = v = c. The second condition is (x * x) % k == 0. This is equivalent to x^2 % k == 0.
3. Find the smallest m such that if x is a multiple of m, then x^2 is a multiple of k.
4. Store a map where the key is (v - c, v % m).
5. As you traverse the string, calculate the current (v - c) and v % m. The number of beautiful substrings ending here is the count of this key in the map.

Example explanation

k = 4. We need x^2 % 4 == 0. This means x must be a multiple of 2. So m = 2.

1. Traverse string. Keep track of balance = vowels - consonants.
2. Keep track of v_count = total_vowels % 2.
3. At each step, lookup (balance, v_count) in our Hash Map.
4. Add the stored frequency to our total answer.
5. Increment the frequency of (balance, v_count) in the map.

Common mistakes candidates make

• Not finding 'm': Trying to use k directly in the map key, which doesn't work because v doesn't have to be a multiple of k for v^2 to be a multiple of k.
• Map Key: Forgetting that both the "vowels == consonants" balance and the "divisibility" condition must be captured in the map key.
• Math Logic: Failing to handle the modulo of negative balances correctly.

Interview preparation tip

Practice finding the "minimum period" m for square divisibility. If k = p1^a1 * p2^a2..., then m is the product of pi ^ ceil(ai / 2). This is a useful number theory trick for "Hard" problems.