Count Beautiful Substrings II solution and explanation
4 more videos on this problem
Count Beautiful Substrings II | Detailed Approach | Intuition | Leetcode - 2949 | Weekly Contest 373codestorywithMIK · 52:40 · 7K views
2949. Count Beautiful Substrings II | Weekly Leetcode 373codingMohan · 38:49 · 2K views
2949. Count Beautiful Substrings II (Leetcode Hard)Programming Live with Larry · 37:47 · 603 views
【每日一题】LeetCode 2949. Count Beautiful Substrings IIHuifeng Guan · 22:32 · 483 views
Count Beautiful Substrings II - LeetCode 2949 - PythonAlpha-Code · 39:54 · 256 views
The problem
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.
Approach 1: Brute Force Approach
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.
def is_vowel(ch):
return ch in 'aeiou'
def count_beautiful_substrings(s, k):
n = len(s)
count = 0
for i in range(n):
vowels = 0
consonants = 0
for j in range(i, n):
if is_vowel(s[j]):
vowels += 1
else:
consonants += 1
if vowels == consonants and (vowels * consonants) % k == 0:
count += 1
return count
# Example usage
s = "baeyh"
k = 2
print(count_beautiful_substrings(s, k))public class Main {
public static boolean isVowel(char ch) {
return "aeiou".indexOf(ch) != -1;
}
public static int countBeautifulSubstrings(String s, int k) {
int n = s.length();
int count = 0;
for (int i = 0; i < n; i++) {
int vowels = 0, consonants = 0;
for (int j = i; j < n; j++) {
if (isVowel(s.charAt(j))) {
vowels++;
} else {
consonants++;
}
if (vowels == consonants && (vowels * consonants) % k == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
String s = "baeyh";
int k = 2;
System.out.println(countBeautifulSubstrings(s, k));
}
}#include <iostream>
#include <string>
using namespace std;
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int countBeautifulSubstrings(const string& s, int k) {
int n = s.size();
int count = 0;
for (int i = 0; i < n; i++) {
int vowels = 0, consonants = 0;
for (int j = i; j < n; j++) {
if (isVowel(s[j])) {
vowels++;
} else {
consonants++;
}
if (vowels == consonants && (vowels * consonants) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
string s = "baeyh";
int k = 2;
cout << countBeautifulSubstrings(s, k) << endl;
return 0;
}function isVowel(ch) {
return 'aeiou'.includes(ch);
}
function countBeautifulSubstrings(s, k) {
let count = 0;
let n = s.length;
for (let i = 0; i < n; i++) {
let vowels = 0;
let consonants = 0;
for (let j = i; j < n; j++) {
if (isVowel(s[j])) {
vowels++;
} else {
consonants++;
}
if (vowels === consonants && (vowels * consonants) % k === 0) {
count++;
}
}
}
return count;
}
console.log(countBeautifulSubstrings('baeyh', 2));#include <stdio.h>
#include <string.h>
int isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int countBeautifulSubstrings(char* s, int k) {
int n = strlen(s);
int count = 0;
for (int i = 0; i < n; i++) {
int vowels = 0, consonants = 0;
for (int j = i; j < n; j++) {
if (isVowel(s[j])) {
vowels++;
} else {
consonants++;
}
if (vowels == consonants && (vowels * consonants) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
char s[] = "baeyh";
int k = 2;
printf("%d\n", countBeautifulSubstrings(s, k));
return 0;
}using System;
public class BeautifulSubstrings {
public static bool IsVowel(char ch) {
return "aeiou".IndexOf(ch) != -1;
}
public static int CountBeautifulSubstrings(string s, int k) {
int n = s.Length;
int count = 0;
for (int i = 0; i < n; i++) {
int vowels = 0, consonants = 0;
for (int j = i; j < n; j++) {
if (IsVowel(s[j])) {
vowels++;
} else {
consonants++;
}
if (vowels == consonants && (vowels * consonants) % k == 0) {
count++;
}
}
}
return count;
}
public static void Main() {
string s = "baeyh";
int k = 2;
Console.WriteLine(CountBeautifulSubstrings(s, k));
}
}The Python solution uses similar nested loops to enumerate substrings and check their properties. Libraries are not necessary for this brute force technique.
Time Complexity: O(n^3).
Space Complexity: O(1).
Approach 2: Optimized Sliding Window or Prefix Array Approach
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.
def is_vowel(ch):
return ch in 'aeiou'
def count_beautiful_substrings(s, k):
n = len(s)
count = 0
prefix_vowels = [0] * (n + 1)
prefix_consonants = [0] * (n + 1)
for i in range(n):
prefix_vowels[i + 1] = prefix_vowels[i] + (1 if is_vowel(s[i]) else 0)
prefix_consonants[i + 1] = prefix_consonants[i] + (1 if not is_vowel(s[i]) else 0)
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length
curr_vowels = prefix_vowels[j] - prefix_vowels[i]
curr_consonants = prefix_consonants[j] - prefix_consonants[i]
if curr_vowels == curr_consonants and (curr_vowels * curr_consonants) % k == 0:
count += 1
return count
# Example usage
s = "baeyh"
k = 2
print(count_beautiful_substrings(s, k))public class Main {
public static boolean isVowel(char ch) {
return "aeiou".indexOf(ch) != -1;
}
public static int countBeautifulSubstrings(String s, int k) {
int n = s.length();
int count = 0;
int[] prefixVowels = new int[n + 1];
int[] prefixConsonants = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixVowels[i + 1] = prefixVowels[i] + (isVowel(s.charAt(i)) ? 1 : 0);
prefixConsonants[i + 1] = prefixConsonants[i] + (!isVowel(s.charAt(i)) ? 1 : 0);
}
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len;
int currVowels = prefixVowels[j] - prefixVowels[i];
int currConsonants = prefixConsonants[j] - prefixConsonants[i];
if (currVowels == currConsonants && (currVowels * currConsonants) % k == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
String s = "baeyh";
int k = 2;
System.out.println(countBeautifulSubstrings(s, k));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int countBeautifulSubstrings(const string& s, int k) {
int n = s.size();
int count = 0;
vector<int> prefixVowels(n + 1, 0);
vector<int> prefixConsonants(n + 1, 0);
for (int i = 0; i < n; i++) {
prefixVowels[i + 1] = prefixVowels[i] + (isVowel(s[i]) ? 1 : 0);
prefixConsonants[i + 1] = prefixConsonants[i] + (!isVowel(s[i]) ? 1 : 0);
}
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len;
int currVowels = prefixVowels[j] - prefixVowels[i];
int currConsonants = prefixConsonants[j] - prefixConsonants[i];
if (currVowels == currConsonants && (currVowels * currConsonants) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
string s = "baeyh";
int k = 2;
cout << countBeautifulSubstrings(s, k) << endl;
return 0;
}function isVowel(ch) {
return 'aeiou'.includes(ch);
}
function countBeautifulSubstrings(s, k) {
let n = s.length;
let count = 0;
let prefixVowels = new Array(n + 1).fill(0);
let prefixConsonants = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefixVowels[i + 1] = prefixVowels[i] + (isVowel(s[i]) ? 1 : 0);
prefixConsonants[i + 1] = prefixConsonants[i] + (!isVowel(s[i]) ? 1 : 0);
}
for (let len = 1; len <= n; len++) {
for (let i = 0; i + len <= n; i++) {
let j = i + len;
let currVowels = prefixVowels[j] - prefixVowels[i];
let currConsonants = prefixConsonants[j] - prefixConsonants[i];
if (currVowels === currConsonants && (currVowels * currConsonants) % k === 0) {
count++;
}
}
}
return count;
}
console.log(countBeautifulSubstrings('baeyh', 2));#include <stdio.h>
#include <string.h>
int isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int countBeautifulSubstrings(char* s, int k) {
int n = strlen(s);
int count = 0;
int vowels = 0, consonants = 0;
int prefixVowels[n + 1];
int prefixConsonants[n + 1];
prefixVowels[0] = 0;
prefixConsonants[0] = 0;
for (int i = 0; i < n; i++) {
if (isVowel(s[i])) {
vowels++;
} else {
consonants++;
}
prefixVowels[i + 1] = vowels;
prefixConsonants[i + 1] = consonants;
}
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len;
int currVowels = prefixVowels[j] - prefixVowels[i];
int currConsonants = prefixConsonants[j] - prefixConsonants[i];
if (currVowels == currConsonants && (currVowels * currConsonants) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
char s[] = "baeyh";
int k = 2;
printf("%d\n", countBeautifulSubstrings(s, k));
return 0;
}using System;
public class BeautifulSubstrings {
public static bool IsVowel(char ch) {
return "aeiou".IndexOf(ch) != -1;
}
public static int CountBeautifulSubstrings(string s, int k) {
int n = s.Length;
int count = 0;
int[] prefixVowels = new int[n + 1];
int[] prefixConsonants = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixVowels[i + 1] = prefixVowels[i] + (IsVowel(s[i]) ? 1 : 0);
prefixConsonants[i + 1] = prefixConsonants[i] + (!IsVowel(s[i]) ? 1 : 0);
}
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len;
int currVowels = prefixVowels[j] - prefixVowels[i];
int currConsonants = prefixConsonants[j] - prefixConsonants[i];
if (currVowels == currConsonants && (currVowels * currConsonants) % k == 0) {
count++;
}
}
}
return count;
}
public static void Main() {
string s = "baeyh";
int k = 2;
Console.WriteLine(CountBeautifulSubstrings(s, k));
}
}Using Python's list operations, this solution calculates cumulative counts of vowels and consonants, allowing for rapid verification of substring conditions.
Time Complexity: O(n^2).
Space Complexity: O(n).
Approach 3: Prefix Sum + Hash Table
function beautifulSubstrings(s: string, k: number): number {
const l = pSqrt(k * 4);
const n = s.length;
let sum = n;
let ans = 0;
const counter = new Map();
counter.set(((l - 1) << 17) | sum, 1);
for (let i = 0; i < n; i++) {
const char = s[i];
const bit = (AEIOU_MASK >> (char.charCodeAt(0) - 'a'.charCodeAt(0))) & 1;
sum += bit * 2 - 1; // 1 -> 1 0 -> -1
const key = ((i % l) << 17) | sum;
ans += counter.get(key) || 0; // ans += cnt[(i%k,sum)]++
counter.set(key, (counter.get(key) ?? 0) + 1);
}
return ans;
}
const AEIOU_MASK = 1065233;
function pSqrt(n: number) {
let res = 1;
for (let i = 2; i * i <= n; i++) {
let i2 = i * i;
while (n % i2 == 0) {
res *= i;
n /= i2;
}
if (n % i == 0) {
res *= i;
n /= i;
}
}
if (n > 1) {
res *= n;
}
return res;
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: |
| Optimized Sliding Window or Prefix Array Approach | Time Complexity: |
| Prefix Sum + Hash Table | – |
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 |
Frequently asked questions
Is Count Beautiful Substrings II easy or hard?
Count Beautiful Substrings II is classified as a Hard problem. The difficulty comes from combining multiple concepts: prefix sums, hash table state compression, and number theory to derive the required substring length constraint.
Count Beautiful Substrings II Python/Java solution
Most implementations use the same algorithm across languages: compute the required period using number theory, maintain a running prefix difference, and store counts in a hash map. The logic translates directly to Python, Java, C++, or other languages with dictionary support.
How to solve Count Beautiful Substrings II in O(n)?
Compute the smallest integer t such that t^2 is divisible by k. While iterating through the string, maintain the prefix difference between vowels and consonants and store counts in a hash map keyed by (diff, index mod 2t). When the same key appears again, it forms valid beautiful substrings.
What is the best approach for Count Beautiful Substrings II?
The optimal approach uses prefix difference with a hash table combined with a number theory observation. Track the difference between vowels and consonants using prefix sums and group indices by (diff, index mod period). This allows counting valid substrings in O(n) time and O(n) space.
Is Count Beautiful Substrings II asked at Google/Amazon/Meta?
Problems involving prefix sums, hash maps, and substring counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this pattern are commonly used to test string processing and prefix-state hashing techniques.
What data structure is used in Count Beautiful Substrings II?
The optimized solution relies on a hash table (hash map) to store counts of prefix states. It also uses prefix sums to track vowel and consonant differences and applies number theory to enforce the divisibility constraint efficiently.
What is the time complexity of Count Beautiful Substrings II?
The brute force method runs in O(n^2) time because it checks every substring. The optimized approach runs in O(n) time by scanning the string once and using hash table lookups to count matching prefix states.