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 <= 10001 <= k <= 1000s consists of only English lowercase letters.To solve #2947 Count Beautiful Substrings I, we need to identify substrings where the number of vowels equals the number of consonants and the product of their counts satisfies the divisibility condition with k. A practical way to approach this is by using prefix sums to quickly compute the number of vowels in any substring. Since consonants can be derived from the substring length, we avoid recomputation.
We can then enumerate all possible substrings. For each substring, compute the vowel and consonant counts using the prefix array. If the counts are equal and the condition (vowels * consonants) % k == 0 holds, we increment the result. Because the constraints are moderate, this enumeration approach works efficiently.
This method leverages string processing, math checks, and prefix sum optimization to reduce repeated counting operations. The overall complexity remains manageable for the given limits.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum + Substring Enumeration | O(n^2) | O(n) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
Iterate over all substrings and maintain the frequencies of vowels and consonants.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like this appear in interviews at large tech companies because they combine string processing, prefix sums, and mathematical reasoning. Even if the exact question isn't asked, similar substring-counting patterns are common in coding interviews.
Prefix sums avoid recalculating vowel counts repeatedly. By storing cumulative counts, we can determine the number of vowels in a substring in O(1) time, which keeps the overall algorithm efficient during enumeration.
A prefix sum array is the most useful structure for this problem. It allows constant-time retrieval of vowel counts for any substring, making the enumeration process much more efficient.
The common approach uses prefix sums combined with substring enumeration. A prefix array helps quickly determine the number of vowels in any substring, and consonants can be derived from the length. Each substring is then checked for equal counts and the divisibility condition with k.