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.To solve #2949 Count Beautiful Substrings II, we must identify substrings where the number of vowels equals the number of consonants and the substring also satisfies a divisibility constraint involving k. Start by converting the string into a prefix difference where vowels contribute +1 and consonants contribute -1. A substring has equal vowels and consonants when the prefix difference at two indices is the same.
The number theory component comes from the condition involving k. If a substring has t vowels and t consonants, its length is 2t and the constraint reduces to ensuring t^2 is divisible by k. By factoring k, we determine the smallest value m such that m^2 is divisible by k. Valid substrings must therefore have lengths divisible by 2m.
While scanning the string, maintain a hash map keyed by (prefixDiff, index mod 2m). Matching states indicate valid substrings. This combination of prefix sums, hashing, and number theory allows counting substrings efficiently in linear time.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum + Hash Map with Number Theory Optimization | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
For the given <code>k</code> find all the <code>x</code> integers such that <code>x^2 % k == 0</code>. Notice, that there aren’t many such candidates.
We can iterate over all such <code>x</codes> values and count the number of substrings such that <code>vowels == consonants == x</code>.
This can be done with prefix sums and hash map.
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
Hard string and prefix-sum problems similar to Count Beautiful Substrings II are common in FAANG-style interviews. They test knowledge of hashing, prefix techniques, and mathematical optimization.
Number theory helps simplify the condition that the product of vowel and consonant counts must be divisible by k. By factoring k, we determine the minimum t such that t^2 is divisible by k, which leads to a substring length divisibility rule.
A hash map is the key data structure for this problem. It stores counts of previously seen prefix states defined by the vowel-consonant difference and the index modulo a derived cycle length.
The optimal approach combines prefix sums with a hash map and number theory. By tracking the difference between vowels and consonants and grouping indices by modulo constraints derived from k, we can count valid substrings in linear time.