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.Problem Overview: You are given a string s and an integer k. A substring is considered beautiful when the number of vowels equals the number of consonants and the product vowels × consonants is divisible by k. The task is to count all such substrings efficiently.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Enumerate every possible substring using two nested loops. While extending the right boundary, maintain running counts of vowels and consonants. Each time the counts become equal, check whether vowels * consonants % k == 0. Since the counts are equal, the product becomes v², where v is the number of vowels. This approach directly follows the definition and is useful for verifying correctness or handling small input sizes. The downside is quadratic time because every substring is evaluated.
Approach 2: Prefix Sum + Hash Map (Optimized Sliding Window Idea) (O(n) time, O(n) space)
The key observation: if vowels equal consonants in a substring, its length must be even. Let v be the number of vowels; the substring length is 2v and the product condition becomes v² % k == 0. Compute the smallest integer r such that r² % k == 0. Any valid substring must then have v as a multiple of r, meaning the substring length must be divisible by 2r.
Use a prefix difference diff = vowels - consonants. When two positions have the same diff, the substring between them has equal vowels and consonants. To enforce the divisibility rule, also track the prefix index modulo 2r. Store counts in a hash table keyed by (diff, index % (2r)). As you iterate through the string, look up how many previous prefixes share the same key and add them to the answer.
This technique combines prefix sum differences with a hash table to count valid substrings in constant time per character. The divisibility rule comes from simple number theory, turning what looks like a nested substring problem into a linear pass.
Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the constraints and conditions. Then derive the prefix-difference observation and the length divisibility rule. Interviewers typically expect the optimized prefix-sum + hash map solution because it reduces the search from O(n²) to O(n) and shows strong pattern recognition with substring counting problems.
This approach involves iterating through all possible substrings of the string s and checking each substring to see if it fulfills the conditions of being a 'beautiful' substring. For each substring, calculate the number of vowels and consonants, then check if the number of vowels equals the number of consonants and their product is divisible by k.
In this C implementation, we define a helper function isVowel() to check if a character is a vowel. We then iterate over all possible substrings of s using two nested loops. For each substring, we maintain counts of vowels and consonants. If a substring satisfies the conditions of being beautiful, we increment the `beautifulCount`.
Time Complexity: O(n^3), because for each of the n starting points, we can have up to n^2 substrings to inspect.
Space Complexity: O(1), as we don't use any additional space beyond the input storage.
This approach makes use of a sliding window technique to optimize substring analysis. By maintaining a running tally of vowels and consonants, and shifting the window, we achieve a more efficient evaluation of substring beauty.
In this C solution, the strategy involves a sliding window-based implementation wherein we repeatedly compute the tally of vowels and consonants, and verify the conditions for the beauty of the substring while moving the window forward through the string.
Time Complexity: O(n^2), optimized from O(n^3) using a sliding window.
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), because for each of the n starting points, we can have up to n^2 substrings to inspect. Space Complexity: O(1), as we don't use any additional space beyond the input storage. |
| Optimized Sliding Window Approach | Time Complexity: O(n^2), optimized from O(n^3) using a sliding window. Space Complexity: O(1) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Good for understanding the problem or when input size is small |
| Prefix Sum + Hash Map (Optimized) | O(n) | O(n) | Best general solution; efficiently counts substrings using prefix differences and modular grouping |
Count Beautiful Substrings I | Simple Approach | Leetcode - 2947 | Weekly Contest 373 • codestorywithMIK • 5,266 views views
Watch 5 more video solutions →Practice Count Beautiful Substrings I with our built-in code editor and test cases.
Practice on FleetCode