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 <= 5 * 1041 <= k <= 1000s consists of only English lowercase letters.Problem Overview: You are given a string and an integer k. A substring is considered beautiful when the number of vowels equals the number of consonants and the product of these counts is divisible by k. The task is to count how many such substrings exist.
Approach 1: Brute Force with Prefix Counts (O(n2) time, O(n) space)
The straightforward solution checks every possible substring. Precompute prefix counts of vowels so you can quickly calculate the number of vowels and consonants in any range. For each pair (i, j), compute vowels and consonants, verify they are equal, then check whether (vowels * consonants) % k == 0. This approach uses prefix sum to avoid recomputing counts, but still requires iterating over all O(n2) substrings. It works for small inputs and helps validate logic before implementing the optimized method.
Approach 2: Prefix Difference + Hash Table with Number Theory (O(n) time, O(n) space)
The key observation: if vowels equal consonants, then v = c. Let v be the number of vowels. The condition becomes v * v % k == 0. Using number theory, compute the smallest integer t such that t * t is divisible by k. That means v must be a multiple of t. Since the substring length is 2v, the length must be divisible by 2t.
While scanning the string, maintain a prefix difference diff = vowels - consonants. Two indices i and j form a valid substring when their diff values match. To enforce the length divisibility constraint, also track the index modulo 2t. Store counts in a hash table keyed by (diff, index % (2t)). When the same key appears again, all previous occurrences represent valid starting points for beautiful substrings ending at the current index. This reduces the problem to constant-time hash lookups per character.
Recommended for interviews: The brute force approach shows you understand the substring conditions and how prefix counts simplify range queries. Interviewers typically expect the optimized prefix-difference solution combined with a hash map and number-theory insight. It reduces the complexity from O(n2) to O(n) and demonstrates strong pattern recognition with prefix states + hashing.
In this approach, we consider all possible substrings of the given string. For each substring, we count the number of vowels and consonants to check if the substring satisfies the conditions to be beautiful.
Iterate over all possible substrings, counting vowels and consonants, and check both conditions for each substring. This approach is straightforward but not very efficient for large strings.
This solution iterates through all possible substrings of the given string s, counting the number of vowels and consonants in each one. When both conditions for a substring to be beautiful are met, the counter is incremented.
Time Complexity: O(n^3) due to the nested iterations for each substring.
Space Complexity: O(1) as no additional space is used aside from counters.
We can optimize the brute force approach by using a sliding window or prefix array technique. The sliding window keeps track of vowel and consonant counts while expanding or contracting the window for each character.
This method reduces redundant recalculations by leveraging previously computed results, improving efficiency by reducing time complexity.
This solution uses prefix sum arrays to keep track of the number of vowels and consonants up to each index. It reduces recalculations by using these prefixes to efficiently determine the number of vowels and consonants in any substring.
Time Complexity: O(n^2) due to double iteration after the prefix sums.
Space Complexity: O(n) due to storing prefix sums.
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: |
| Optimized Sliding Window or Prefix Array Approach | Time Complexity: |
| Prefix Sum + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Prefix Counts | O(n²) | O(n) | Small inputs or when validating substring conditions during learning |
| Prefix Difference + Hash Table + Number Theory | O(n) | O(n) | Optimal approach for large strings and typical interview expectations |
Count Beautiful Substrings II | Detailed Approach | Intuition | Leetcode - 2949 | Weekly Contest 373 • codestorywithMIK • 6,848 views views
Watch 4 more video solutions →Practice Count Beautiful Substrings II with our built-in code editor and test cases.
Practice on FleetCode