Skip to main content
Talentd

Count Beautiful Substrings II - Solution & Explanation

HardHash TableMathStringNumber Theory16 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 <= 5 * 104
  • 1 <= k <= 1000
  • s consists 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.

This solution iterates through all possible substrings of the given string s, counting the number of vowels and consonants in each one. When both conditions for a substring to be beautiful are met, the counter is incremented.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) due to the nested iterations for each substring.
Space Complexity: O(1) as no additional space is used aside from counters.

Try this approach in the editor ā†’

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.

This solution uses prefix sum arrays to keep track of the number of vowels and consonants up to each index. It reduces recalculations by using these prefixes to efficiently determine the number of vowels and consonants in any substring.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to double iteration after the prefix sums.
Space Complexity: O(n) due to storing prefix sums.

Try this approach in the editor ā†’

Approach 3: Prefix Sum + Hash Table

Code

TypeScript

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^3) due to the nested iterations for each substring.
Space Complexity: O(1) as no additional space is used aside from counters.

Optimized Sliding Window or Prefix Array Approach

Time Complexity: O(n^2) due to double iteration after the prefix sums.
Space Complexity: O(n) due to storing prefix sums.

Prefix Sum + Hash Tableā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Prefix CountsO(nĀ²)O(n)Small inputs or when validating substring conditions during learning
Prefix Difference + Hash Table + Number TheoryO(n)O(n)Optimal approach for large strings and typical interview expectations

Video Solution

Count Beautiful Substrings II | Detailed Approach | Intuition | Leetcode - 2949 | Weekly Contest 373 ā€¢ codestorywithMIK ā€¢ 7,387 views views

Watch 4 more video solutions ā†’

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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters