Count Beautiful Substrings II

Hard

Asked by:

2 views

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 <= 5 * 10⁴
1 <= k <= 1000
s consists of only English lowercase letters.

Try coding it in LeetCode

Count Beautiful Substrings II

Hard

Asked by:

2 views

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 <= 5 * 10⁴
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 definition of a 'beautiful substring' in this context? What are the precise criteria it must satisfy?
What are the constraints on the length of the input string, and the values of 'k'? Can I assume they will always be positive integers?
Can the input string contain characters other than lowercase English vowels and consonants? If so, how should I handle them?
If no beautiful substrings exist, what should the function return?
Are overlapping substrings considered distinct when counting, or should each character only belong to one beautiful substring?

Brute Force Solution

Approach

The brute force method for counting beautiful substrings considers every possible substring. For each substring, we simply check if it meets the 'beautiful' criteria and then count it if it does. This method ensures we find all possible beautiful substrings but is not very efficient.

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

Start with the shortest possible substrings (just one character each).
Check if each of these single-character substrings is 'beautiful' according to the given rules.
Then, consider all substrings of length two (pairs of characters).
Again, check if each of these two-character substrings is 'beautiful'.
Continue this process, increasing the substring length one character at a time.
For each possible substring length, examine all substrings of that length that exist within the original string.
Every time you find a substring that satisfies the 'beautiful' condition, increase the count of beautiful substrings.
Finally, after checking all possible substrings of all possible lengths, report the final count of beautiful substrings.

Code Implementation

def count_beautiful_substrings_brute_force(input_string, beautiful_number):
    string_length = len(input_string)
    beautiful_substring_count = 0

    for substring_length in range(1, string_length + 1):

        # Iterate through all possible start indices for each substring length
        for start_index in range(string_length - substring_length + 1):
            end_index = start_index + substring_length
            substring = input_string[start_index:end_index]

            vowel_count = 0
            consonant_count = 0

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

            # Check if the substring meets the 'beautiful' criteria.
            if vowel_count * consonant_count == beautiful_number:
                beautiful_substring_count += 1

    return beautiful_substring_count

Big(O) Analysis

Time Complexity

O(n³) – The described brute force approach iterates through all possible substrings of the given string. The outer loop implicitly considers substring lengths from 1 to n. For each substring length, we iterate through all possible starting positions for substrings of that length. This means we have nested loops. In the innermost part, to check if a substring is beautiful, we need to count the number of vowels and consonants, which requires iterating through the characters of the substring. This gives us a time complexity of O(n * n * n) or O(n³), where n is the length of the input string.

Space Complexity

O(1) – The brute force solution described iterates through all possible substrings. While it implicitly uses space to hold substrings being considered, these are typically created using string slicing or similar mechanisms which do not continuously allocate a large amount of auxiliary space. The primary space used is for a constant number of variables such as loop counters or temporary storage for checking if a substring is beautiful, independent of the input string's length N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The core idea is to avoid redundant counting by focusing on the differences between the number of vowels and consonants in substrings. We use a mathematical relationship to link these differences with the given value of 'k' to efficiently count 'beautiful' substrings. The whole process revolves around tracking the cumulative difference between vowels and consonants.

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

Calculate the cumulative difference between the number of vowels and consonants at each position in the string.
Figure out what the vowel-consonant difference needs to be for a substring to be beautiful. This relies on the rule that the number of vowels times consonants equals a specified number (k).
Keep track of how many times each difference value appears as you move through the string.
Use that knowledge to count the 'beautiful' substrings very quickly. The count is incremented based on how many times we have seen the appropriate vowel-consonant difference.
By remembering counts instead of recalculating, we solve the problem efficiently.

Code Implementation

def count_beautiful_substrings(input_string, k_value):
    string_length = len(input_string)
    cumulative_difference = 0
    difference_counts = {0: 1}
    beautiful_substring_count = 0

    for index in range(string_length):
        char = input_string[index]
        if char in 'aeiou':
            cumulative_difference += 1
        else:
            cumulative_difference -= 1

        # Iterate through possible substring lengths to find beautiful substrings
        for substring_length in range(1, string_length + 1):
            if (substring_length * substring_length) % k_value == 0:
                factor = (substring_length * substring_length) // k_value

                # This calculation is for difference needed for beautiful substring
                if factor != 0 and k_value != 0:
                    needed_difference = cumulative_difference - substring_length // factor
                else:
                    needed_difference = cumulative_difference

                # This is where the efficiency comes from: counting seen diffs
                if needed_difference in difference_counts:
                    beautiful_substring_count += difference_counts[needed_difference]

        if cumulative_difference in difference_counts:
            difference_counts[cumulative_difference] += 1
        else:
            difference_counts[cumulative_difference] = 1

    return beautiful_substring_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n once to calculate the cumulative difference between vowels and consonants. A hash map (or dictionary) is used to store the counts of these differences. Accessing and updating the hash map takes constant time on average. Therefore, the time complexity is dominated by the single loop, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm keeps track of how many times each difference value appears in a hash map or similar data structure. In the worst-case scenario, where the vowel-consonant difference is unique for each prefix of the string, the size of this data structure can grow linearly with the length of the string, N. Thus, the auxiliary space required to store these counts is proportional to N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty string input	Return 0, as an empty string has no substrings
k is zero	Iterate through all substrings and count those with equal vowels and consonants which would result in a count increase of 0 * num substrings; effectively, count all substrings with equal vowel and consonants.
k is negative	Return 0, since the product of substring length and the counts of vowels/consonants would also be negative.
String with only vowels or only consonants	If k > 0, the count should be zero, as no substring can have an equal number of vowels and consonants; If k is zero, count substrings that have equal number of vowels and consonants.
Very long string leading to integer overflow in counts	Use 64-bit integers (long) to store the counts and the result to prevent potential overflow.
String with maximum length (e.g., 10^5) and large k value	Ensure the solution's time complexity is optimized to avoid exceeding time limits, potentially using prefix sums and hashmaps.
String contains non-alphabetic characters	Ignore non-alphabetic characters or throw an IllegalArgumentException, as vowel/consonant classification is undefined for them.
k is extremely large leading to integer overflow when multiplied by the length of substring and the number of equal pairs.	Check for overflow before multiplying k to prevent wrong result using BigInteger or return maximum possible integer.