Watch 5 video solutions for Count Beautiful Substrings II, a hard level problem involving Hash Table, Math, String. This walkthrough by codestorywithMIK has 6,848 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |