Count Beautiful Substrings I solution and explanation
4 more videos on this problem
Count Beautiful Substrings I | Simple Approach | Leetcode - 2947 | Weekly Contest 373codestorywithMIK · 15:13 · 6K views
2947. Count Beautiful Substrings I (Leetcode Medium)Programming Live with Larry · 3:58 · 294 views
2947. Count Beautiful Substrings | Leetcode Weekly Contest 373Shivam Mishra LeetCode · 7:23 · 144 views
Count Beautiful Substrings I - LeetCode 2947 - PythonAlpha-Code · 6:47 · 96 views
2947. Count Beautiful Substrings I (Exaplanation) || LeetcodeX AlphA - Hard Algorithms · 6:21 · 96 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 <= 10001 <= k <= 1000sconsists of only English lowercase letters.
Approach overview
Problem Overview: You are given a string s and an integer k. A substring is considered beautiful when the number of vowels equals the number of consonants and the product vowels × consonants is divisible by k. The task is to count all such substrings efficiently.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Enumerate every possible substring using two nested loops. While extending the right boundary, maintain running counts of vowels and consonants. Each time the counts become equal, check whether vowels * consonants % k == 0. Since the counts are equal, the product becomes v², where v is the number of vowels. This approach directly follows the definition and is useful for verifying correctness or handling small input sizes. The downside is quadratic time because every substring is evaluated.
Approach 2: Prefix Sum + Hash Map (Optimized Sliding Window Idea) (O(n) time, O(n) space)
The key observation: if vowels equal consonants in a substring, its length must be even. Let v be the number of vowels; the substring length is 2v and the product condition becomes v² % k == 0. Compute the smallest integer r such that r² % k == 0. Any valid substring must then have v as a multiple of r, meaning the substring length must be divisible by 2r.
Use a prefix difference diff = vowels - consonants. When two positions have the same diff, the substring between them has equal vowels and consonants. To enforce the divisibility rule, also track the prefix index modulo 2r. Store counts in a hash table keyed by (diff, index % (2r)). As you iterate through the string, look up how many previous prefixes share the same key and add them to the answer.
This technique combines prefix sum differences with a hash table to count valid substrings in constant time per character. The divisibility rule comes from simple number theory, turning what looks like a nested substring problem into a linear pass.
Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the constraints and conditions. Then derive the prefix-difference observation and the length divisibility rule. Interviewers typically expect the optimized prefix-sum + hash map solution because it reduces the search from O(n²) to O(n) and shows strong pattern recognition with substring counting problems.
Approach 1: Brute Force Approach
This approach involves iterating through all possible substrings of the string s and checking each substring to see if it fulfills the conditions of being a 'beautiful' substring. For each substring, calculate the number of vowels and consonants, then check if the number of vowels equals the number of consonants and their product is divisible by k.
def is_vowel(c):
return c in 'aeiou'
def count_beautiful_substrings(s, k):
beautiful_count = 0
length = len(s)
for start in range(length):
vowels = 0
consonants = 0
for end in range(start, length):
if is_vowel(s[end]):
vowels += 1
else:
consonants += 1
if vowels == consonants and (vowels * consonants) % k == 0:
beautiful_count += 1
return beautiful_count
# Example usage
s = "baeyh"
k = 2
print(count_beautiful_substrings(s, k))public class BeautifulSubstrings {
public static void main(String[] args) {
String s = "baeyh";
int k = 2;
System.out.println(countBeautifulSubstrings(s, k));
}
public static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public static int countBeautifulSubstrings(String s, int k) {
int beautifulCount = 0;
int length = s.length();
for (int start = 0; start < length; start++) {
int vowels = 0, consonants = 0;
for (int end = start; end < length; end++) {
if (isVowel(s.charAt(end)))
vowels++;
else
consonants++;
if (vowels == consonants && (vowels * consonants) % k == 0)
beautifulCount++;
}
}
return beautifulCount;
}
}#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countBeautifulSubstrings(string s, int k) {
int beautifulCount = 0;
int length = s.length();
for (int start = 0; start < length; ++start) {
int vowels = 0, consonants = 0;
for (int end = start; end < length; ++end) {
if (isVowel(s[end]))
++vowels;
else
++consonants;
if (vowels == consonants && (vowels * consonants) % k == 0)
++beautifulCount;
}
}
return beautifulCount;
}
int main() {
string s = "baeyh";
int k = 2;
cout << countBeautifulSubstrings(s, k) << endl;
return 0;
}function isVowel(c) {
return 'aeiou'.includes(c);
}
function countBeautifulSubstrings(s, k) {
let beautifulCount = 0;
let length = s.length;
for (let start = 0; start < length; start++) {
let vowels = 0, consonants = 0;
for (let end = start; end < length; end++) {
if (isVowel(s[end]))
vowels++;
else
consonants++;
if (vowels === consonants && (vowels * consonants) % k === 0)
beautifulCount++;
}
}
return beautifulCount;
}
// Example usage:
const s = "baeyh";
const k = 2;
console.log(countBeautifulSubstrings(s, k));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countBeautifulSubstrings(char* s, int k) {
int length = strlen(s);
int beautifulCount = 0;
for (int start = 0; start < length; start++) {
int vowels = 0, consonants = 0;
for (int end = start; end < length; end++) {
if (isVowel(s[end])) {
vowels++;
} else {
consonants++;
}
if (vowels == consonants && (vowels * consonants) % k == 0) {
beautifulCount++;
}
}
}
return beautifulCount;
}
int main() {
char s[] = "baeyh";
int k = 2;
printf("%d\n", countBeautifulSubstrings(s, k));
return 0;
}using System;
class Solution {
static bool IsVowel(char c) {
return "aeiou".IndexOf(c) != -1;
}
static int CountBeautifulSubstrings(string s, int k) {
int beautifulCount = 0;
int length = s.Length;
for (int start = 0; start < length; start++) {
int vowels = 0, consonants = 0;
for (int end = start; end < length; end++) {
if (IsVowel(s[end]))
vowels++;
else
consonants++;
if (vowels == consonants && (vowels * consonants) % k == 0)
beautifulCount++;
}
}
return beautifulCount;
}
public static void Main() {
string s = "baeyh";
int k = 2;
Console.WriteLine(CountBeautifulSubstrings(s, k));
}
}In Python, define a helper function is_vowel to determine if a character is a vowel. Loop through every possible substring, keeping a tally of vowels and consonants. Verify that the substring is beautiful before counting it.
Time Complexity: O(n^3)
Space Complexity: O(1)
Approach 2: Optimized Sliding Window Approach
This approach makes use of a sliding window technique to optimize substring analysis. By maintaining a running tally of vowels and consonants, and shifting the window, we achieve a more efficient evaluation of substring beauty.
def is_vowel(c):
return c in 'aeiou'
def count_beautiful_substrings_sliding_window(s, k):
beautiful_count = 0
n = len(s)
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:
beautiful_count += 1
return beautiful_count
# Example usage
s = "baeyh"
k = 2
print(count_beautiful_substrings_sliding_window(s, k))public class BeautifulSubstrings {
public static void main(String[] args) {
String s = "baeyh";
int k = 2;
System.out.println(countBeautifulSubstringsSlidingWindow(s, k));
}
public static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public static int countBeautifulSubstringsSlidingWindow(String s, int k) {
int n = s.length();
int beautifulCount = 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)
beautifulCount++;
}
}
return beautifulCount;
}
}#include <iostream>
#include <string>
using namespace std;
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countBeautifulSubstringsSlidingWindow(string s, int k) {
int n = s.length();
int beautifulCount = 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)
++beautifulCount;
}
}
return beautifulCount;
}
int main() {
string s = "baeyh";
int k = 2;
cout << countBeautifulSubstringsSlidingWindow(s, k) << endl;
return 0;
}function isVowel(c) {
return 'aeiou'.includes(c);
}
function countBeautifulSubstringsSlidingWindow(s, k) {
let beautifulCount = 0;
let n = s.length;
for (let i = 0; i < n; i++) {
let vowels = 0, consonants = 0;
for (let j = i; j < n; j++) {
if (isVowel(s[j]))
vowels++;
else
consonants++;
if (vowels === consonants && (vowels * consonants) % k === 0)
beautifulCount++;
}
}
return beautifulCount;
}
// Example usage:
const s = "baeyh";
const k = 2;
console.log(countBeautifulSubstringsSlidingWindow(s, k));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countBeautifulSubstringsSlidingWindow(char* s, int k) {
int n = strlen(s);
int beautifulCount = 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)
beautifulCount++;
}
}
return beautifulCount;
}
int main() {
char s[] = "baeyh";
int k = 2;
printf("%d\n", countBeautifulSubstringsSlidingWindow(s, k));
return 0;
}using System;
class Solution {
static bool IsVowel(char c) {
return "aeiou".IndexOf(c) != -1;
}
static int CountBeautifulSubstringsSlidingWindow(string s, int k) {
int beautifulCount = 0;
int n = s.Length;
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)
beautifulCount++;
}
}
return beautifulCount;
}
public static void Main() {
string s = "baeyh";
int k = 2;
Console.WriteLine(CountBeautifulSubstringsSlidingWindow(s, k));
}
}Using Python, the sliding window optimizes substring inspections by swiftly updating counts and validating beauty conditions continuously rather than recalculating from scratch each time the window moves.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 3: Enumeration
We enumerate the starting position i of the substring in the range [0, n), and the ending position j in the range [i, n), count the number of vowels and consonants in the substring s[i \dots j], and check whether it is a beautiful substring. If so, we increment the answer by 1.
The time complexity is O(n^2), where n is the length of the string. The space complexity is O(1).
function beautifulSubstrings(s: string, k: number): number {
const n = s.length;
const vs: number[] = Array(26).fill(0);
for (const c of 'aeiou') {
vs[c.charCodeAt(0) - 'a'.charCodeAt(0)] = 1;
}
let ans = 0;
for (let i = 0; i < n; ++i) {
let vowels = 0;
for (let j = i; j < n; ++j) {
vowels += vs[s.charCodeAt(j) - 'a'.charCodeAt(0)];
const consonants = j - i + 1 - vowels;
if (vowels === consonants && (vowels * consonants) % k === 0) {
++ans;
}
}
}
return ans;
}func beautifulSubstrings(s string, k int) (ans int) {
n := len(s)
vs := [26]int{}
for _, c := range "aeiou" {
vs[c-'a'] = 1
}
for i := 0; i < n; i++ {
vowels := 0
for j := i; j < n; j++ {
vowels += vs[s[j]-'a']
consonants := j - i + 1 - vowels
if vowels == consonants && vowels*consonants%k == 0 {
ans++
}
}
}
return
}impl Solution {
pub fn beautiful_substrings(s: String, k: i32) -> i32 {
let n = s.len();
let s = s.as_bytes();
let mut vs = [0; 26];
for &c in b"aeiou" {
vs[(c - b'a') as usize] = 1;
}
let mut ans = 0;
for i in 0..n {
let mut vowels = 0;
for j in i..n {
vowels += vs[(s[j] - b'a') as usize];
let consonants = (j - i + 1) as i32 - vowels;
if vowels == consonants && (vowels * consonants) % k == 0 {
ans += 1;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) Space Complexity: O(1) |
| Optimized Sliding Window Approach | Time Complexity: O(n^2) Space Complexity: O(1) |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Good for understanding the problem or when input size is small |
| Prefix Sum + Hash Map (Optimized) | O(n) | O(n) | Best general solution; efficiently counts substrings using prefix differences and modular grouping |
Frequently asked questions
Is Count Beautiful Substrings I easy or hard?
Count Beautiful Substrings I is rated Medium. The brute force idea is straightforward, but deriving the mathematical constraint and combining it with prefix sums and hashing requires deeper problem-solving and pattern recognition.
Count Beautiful Substrings I Python/Java solution
Both Python and Java implementations follow the same structure: compute prefix differences, calculate the required modulus length (2r), and store prefix states in a hash map. Each step performs constant-time updates and lookups, leading to an O(n) implementation.
How to solve Count Beautiful Substrings I in O(n)?
Compute a prefix difference between vowels and consonants while scanning the string. Determine the smallest integer r where r² is divisible by k, which implies valid substring lengths must be multiples of 2r. Use a hash map keyed by (prefix difference, index mod 2r) to count how many previous prefixes can form a beautiful substring with the current position.
What is the best approach for Count Beautiful Substrings I?
The most efficient approach uses prefix sums with a hash map. Track the difference between vowels and consonants using a running prefix value. Combine this with index modulo constraints derived from the divisibility condition v² % k == 0. This allows counting valid substrings in O(n) time instead of checking all O(n²) substrings.
Is Count Beautiful Substrings I asked at Google/Amazon/Meta?
Substring counting problems using prefix sums and hash maps frequently appear in interviews at companies like Amazon, Google, and Meta. Variations that involve vowel/consonant balance and modular constraints test both string processing and mathematical reasoning.
What data structure is used in Count Beautiful Substrings I?
The optimized solution primarily uses a hash table (hash map) to store counts of prefix states. It also relies on prefix sum techniques to track vowel–consonant differences and number theory insights to enforce the divisibility constraint.
What is the time complexity of Count Beautiful Substrings I?
The brute force approach runs in O(n²) time because it evaluates every substring. The optimized solution using prefix sums and a hash map processes each character once and performs constant-time lookups, resulting in O(n) time and O(n) space complexity.