Skip to main content
Talentd

Count Beautiful Substrings I - Solution & Explanation

MediumHash TableMathStringEnumeration19 min readAsked at: Amazon
Practice this problem

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 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 <= 1000
  • 1 <= k <= 1000
  • s consists 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.

In this C implementation, we define a helper function isVowel() to check if a character is a vowel. We then iterate over all possible substrings of s using two nested loops. For each substring, we maintain counts of vowels and consonants. If a substring satisfies the conditions of being beautiful, we increment the `beautifulCount`.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3), because for each of the n starting points, we can have up to n^2 substrings to inspect.

Space Complexity: O(1), as we don't use any additional space beyond the input storage.

Try this approach in the editor →

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.

In this C solution, the strategy involves a sliding window-based implementation wherein we repeatedly compute the tally of vowels and consonants, and verify the conditions for the beauty of the substring while moving the window forward through the string.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), optimized from O(n^3) using a sliding window.

Space Complexity: O(1)

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^3), because for each of the n starting points, we can have up to n^2 substrings to inspect.

Space Complexity: O(1), as we don't use any additional space beyond the input storage.

Optimized Sliding Window Approach

Time Complexity: O(n^2), optimized from O(n^3) using a sliding window.

Space Complexity: O(1)

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(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

Video Solution

Count Beautiful Substrings I | Simple Approach | Leetcode - 2947 | Weekly Contest 373 • codestorywithMIK • 6,157 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Count Beautiful Substrings I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters