Count Beautiful Substrings II - Video Solutions
Count Beautiful Substrings II | Detailed Approach | Intuition | Leetcode - 2949 | Weekly Contest 373
Count Beautiful Substrings II - Video Solution
Watch 5 video solutions for Count Beautiful Substrings II, a hard level problem involving Hash Table, Math, String. This walkthrough by codestorywithMIK has 7,387 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 ofvowelsandconsonantsis divisible byk.
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 <= 1000sconsists of only English lowercase letters.
Approach Overview
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.
Complexity Analysis
| 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 |