Count Beautiful Substrings I

Count Beautiful Substrings I

What is this problem about?

The Count Beautiful Substrings I interview question asks you to count the number of non-empty substrings in a given string s that are "beautiful." A substring is beautiful if:

1. The number of vowels equals the number of consonants.
2. The product of the number of vowels and the number of consonants is divisible by a given integer k.

Why is this asked in interviews?

Amazon uses this String interview pattern to test your ability to handle multiple constraints and optimize substring searches. Since this is version "I" of the problem, the constraints are usually small enough for an O(N^2) solution. It evaluates your basic string manipulation and modular arithmetic knowledge.

Algorithmic pattern used

The pattern is Brute Force with Enumeration.

1. Iterate through all possible starting positions i.
2. Iterate through all possible ending positions j.
3. For each substring s[i..j], count the vowels and consonants.
4. Check if vowels == consonants AND (vowels * consonants) % k == 0.
5. Keep a running total.

Example explanation

s = "baeyh", k = 2 Substrings:

• "ae": Vowels=2, Consonants=0. No.
• "ba": Vowels=1, Consonants=1. 1*1 = 1. 1 % 2 != 0. No.
• "baey": Vowels=2, Consonants=2. 2*2 = 4. 4 % 2 == 0. Yes! Result: 1.

Common mistakes candidates make

• Definition of Vowels: Forgetting that 'y' is usually not considered a vowel in these coding problems (a, e, i, o, u).
• Efficiency: Calculating vowels/consonants from scratch for every substring instead of updating them as you extend the substring (O(N^2) vs O(N^3)).
• Divisibility: Mixing up the conditions—both must be true for the substring to be beautiful.

Interview preparation tip

Even if the O(N^2) solution passes, always mention how you could optimize it using a Hash Map and Prefix Sums. This leads directly into the "Hard" version of this problem.