Count Beautiful Substrings I

Medium

Asked by:

1 view

Topics:

Strings

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.

Try coding it in LeetCode

Count Beautiful Substrings I

Medium

Asked by:

1 view

Topics:

Strings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`?
Is the input string `s` case-sensitive?
What are the possible values for `k`? Is `k` always a positive integer?
What constitutes a 'beautiful' substring according to the provided definition (equal number of vowels and consonants multiplied by `k`)?
If no beautiful substrings exist, what should the function return? Should it return 0, or should an exception be thrown?

Brute Force Solution

Approach

The brute force strategy for this problem involves checking every possible substring within the given word. We will go through each substring, one by one, to see if it meets the 'beautiful' criteria. This means exhaustively checking all possibilities to ensure we don't miss any solutions.

Here's how the algorithm would work step-by-step:

Consider the first letter of the word as a possible substring.
Then consider the first two letters, then the first three, and so on, until you've considered a substring that includes the entire word.
Now, start again with the second letter as the beginning of a substring. Consider just the second letter, then the second and third letters, then the second, third, and fourth letters, and so on.
Continue this process, shifting the starting point of the substring one letter at a time, until you've considered the very last letter of the word as a substring on its own.
For each substring you consider, check if it meets the criteria to be 'beautiful' (same amount of vowels and consonants and length is a multiple of a given number).
If a substring is 'beautiful', increase a counter to track how many 'beautiful' substrings you have found.
After you've checked every possible substring, the counter will hold the total number of 'beautiful' substrings.

Code Implementation

def count_beautiful_substrings(word, k):
    word_length = len(word)
    beautiful_substring_count = 0

    for start_index in range(word_length):
        for end_index in range(start_index, word_length):
            substring = word[start_index:end_index + 1]
            substring_length = len(substring)

            vowel_count = 0
            consonant_count = 0

            for char in substring:
                if char in 'aeiou':
                    vowel_count += 1
                else:
                    consonant_count += 1

            # Check if substring meets the beautiful criteria
            if vowel_count == consonant_count:

                #Also check for length requirement
                if substring_length % k == 0:
                    beautiful_substring_count += 1

    return beautiful_substring_count

Big(O) Analysis

Time Complexity

O(n²) – The described brute force solution iterates through all possible substrings of the input word. The outer loop iterates from the beginning of the word (index 0) to the end (index n-1), where n is the length of the word. The inner loop then expands the substring from the current starting index to the end of the word. Therefore, for each starting position, the inner loop iterates up to n times. This results in approximately n * n/2 operations to generate all substrings and check their beauty, simplifying to a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach iterates through all substrings without using any auxiliary data structures that scale with the input size. Temporary variables might be used within the inner loop to count vowels and consonants, but their memory usage remains constant irrespective of the input string's length, N. Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to efficiently count special substrings within a given string based on the counts of vowels and consonants. The clever trick is to recognize that we only need to check substrings whose length is a multiple of a given number, and keep track of running counts to quickly check this condition.

Here's how the algorithm would work step-by-step:

Figure out the given number based on the problem description.
Go through the string, looking at substrings that start at each position.
For each starting position, only consider substrings whose length is a multiple of the previously computed number.
For each of these substrings, quickly count the number of vowels and consonants.
If the vowel and consonant counts are the same, increment a counter.
After checking all starting positions and their relevant substrings, return the counter. This is the number of beautiful substrings.

Code Implementation

def count_beautiful_substrings(word, k):
    string_length = len(word)
    beautiful_substring_count = 0
    multiple = k

    for start_index in range(string_length):
        for end_index in range(start_index + 1, string_length + 1):
            substring_length = end_index - start_index

            # Only consider lengths that are multiples of k
            if substring_length % multiple == 0:

                vowel_count = 0
                consonant_count = 0

                # Count vowels and consonants in the substring
                for char_index in range(start_index, end_index):
                    character = word[char_index]
                    if character in 'aeiou':
                        vowel_count += 1
                    else:
                        consonant_count += 1

                # Increment if vowel and consonant counts are the same
                if vowel_count == consonant_count:
                    beautiful_substring_count += 1

    return beautiful_substring_count

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates 'n' times, once for each starting position in the string. The inner loop iterates a maximum of 'n' times, considering substrings whose length is a multiple of some constant. The vowel and consonant counting within the inner loop takes constant time. Therefore, the dominant factor is the nested loop structure, leading to approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only needs to store a few integer variables: loop counters, the vowel count, the consonant count, and the final beautiful substring counter. The space used by these variables does not depend on the size of the input string N, thus the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string input	Return 0 immediately as there are no substrings to evaluate.
String with length 1	Return 0 immediately as a substring must have length > 0 and satisfy the condition
String with very large length (close to maximum allowed)	Ensure algorithm has linear time complexity O(n) to prevent timeouts or excessive memory use when string length is large.
String with all vowels or all consonants	The inner loop should iterate correctly even when vowels and consonants are not mixed.
k is zero	Return 0 immediately since any substring will have 0 * number of vowels * number of consonants equal to 0, and can never be equal to k unless the substring contains no vowels or consonants
k is negative	Return 0 immediately since vowels * consonants will always be non-negative
k is extremely large	Avoid potential integer overflow during multiplication by checking if vowel_count * consonant_count exceeds the maximum possible integer value before comparing with k.
String containing non-alphabetic characters	Ignore non-alphabetic characters when counting vowels and consonants.