#2947

Medium

LeetCode Problem Workspace

Count Beautiful Substrings I

Given a string and a value k, count the number of beautiful substrings where vowels * consonants % k == 0.

hash table math string enumeration number theory

Problem Statement

You are given a string s and a positive integer k. A string is considered beautiful if the product of the number of vowels and consonants in that substring modulo k equals zero.

Your task is to count how many substrings of s are beautiful. A substring is a contiguous sequence of characters within the string. For each substring, if the condition of vowel * consonant % k == 0 holds, it is deemed beautiful.

Examples

Example 1

Input: s = "baeyh", k = 2

Output: 2

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

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

There are no beautiful substrings in the given string.

Constraints

1 <= s.length <= 1000
1 <= k <= 1000
s consists of only English lowercase letters.

Solution Approach

Iterate Through All Substrings

First, iterate over all possible substrings of the given string s. For each substring, calculate the number of vowels and consonants.

Track Frequency with a Hash Table

Use a hash table to keep track of the frequency of vowels and consonants as you move through the string. This enables efficient recalculation of the counts without needing to recompute them from scratch for every substring.

Check Beautiful Substring Condition

For each substring, check if the product of the number of vowels and consonants is divisible by k. If the condition holds, count the substring as beautiful.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the number of substrings, which is O(n^2) for a string of length n. The space complexity is primarily determined by the hash table used to track vowel and consonant counts, which has a space complexity of O(n). Optimizations can reduce this to improve performance for large inputs.

What Interviewers Usually Probe

Does the candidate show an understanding of hash table use in optimization?
Is the candidate capable of correctly identifying when a substring satisfies the condition?
How well does the candidate handle the substring enumeration efficiently?

Common Pitfalls or Variants

Common pitfalls

Overcalculating vowel and consonant counts for every substring from scratch, which leads to a higher time complexity.
Failing to account for edge cases, such as when there are no vowels or consonants.
Incorrectly interpreting the problem's condition, leading to counting invalid substrings.

Follow-up variants

Modify the problem by changing the condition to check for a different mathematical property, such as the sum of vowels and consonants modulo k.
Extend the problem to count substrings that are beautiful and also palindromes.
Change the problem to find the longest beautiful substring instead of counting all beautiful substrings.

FAQ

What is the definition of a beautiful substring in the Count Beautiful Substrings I problem?

A beautiful substring is a substring where the product of the number of vowels and consonants modulo k equals zero.

How can I optimize the solution for Count Beautiful Substrings I?

Use a hash table to track vowel and consonant frequencies to avoid redundant recalculations, making the algorithm more efficient.

What pattern is used in the Count Beautiful Substrings I problem?

The primary pattern involves using hash tables and math to efficiently count substrings that satisfy the condition of the product of vowels and consonants modulo k.

What is the time complexity of the solution to Count Beautiful Substrings I?

The time complexity is O(n^2) due to the enumeration of substrings, where n is the length of the string.

Are there any edge cases I should consider when solving Count Beautiful Substrings I?

Yes, consider edge cases where the string contains no vowels or no consonants, and ensure to handle small strings properly.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        vs = set("aeiou")
        ans = 0
        for i in range(n):
            vowels = 0
            for j in range(i, n):
                vowels += s[j] in vs
                consonants = j - i + 1 - vowels
                if vowels == consonants and vowels * consonants % k == 0:
                    ans += 1
        return ans

Continue Practicing

#2949 count beautiful substrings ii #3044 most frequent prime #3312 sorted gcd pair queries