Find Most Frequent Vowel and Consonant

Easy

Google

8 views

Topics:

Strings

You are given a string s consisting of lowercase English letters ('a' to 'z'). Your task is to:

Find the vowel (one of 'a', 'e', 'i', 'o', or 'u') with the maximum frequency.
Find the consonant (all other letters excluding vowels) with the maximum frequency.

Return the sum of the two frequencies.

Note: If multiple vowels or consonants have the same maximum frequency, you may choose any one of them. If there are no vowels or no consonants in the string, consider their frequency as 0. The frequency of a letter x is the number of times it occurs in the string.

Example 1:

Input: s = "successes" Output: 6

Explanation:

The vowels are: 'u' (frequency 1), 'e' (frequency 2). The maximum frequency is 2.
The consonants are: 's' (frequency 4), 'c' (frequency 2). The maximum frequency is 4.
The output is 2 + 4 = 6.

Example 2:

Input: s = "aeiaeia" Output: 3

Explanation:

The vowels are: 'a' (frequency 3), 'e' ( frequency 2), 'i' (frequency 2). The maximum frequency is 3.
There are no consonants in s. Hence, maximum consonant frequency = 0.
The output is 3 + 0 = 3.

Constraints:

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

Find Most Frequent Vowel and Consonant

Easy

Google

8 views

Topics:

Strings

You are given a string s consisting of lowercase English letters ('a' to 'z'). Your task is to:

Find the vowel (one of 'a', 'e', 'i', 'o', or 'u') with the maximum frequency.
Find the consonant (all other letters excluding vowels) with the maximum frequency.

Return the sum of the two frequencies.

Note: If multiple vowels or consonants have the same maximum frequency, you may choose any one of them. If there are no vowels or no consonants in the string, consider their frequency as 0. The frequency of a letter x is the number of times it occurs in the string.

Example 1:

Input: s = "successes" Output: 6

Explanation:

The vowels are: 'u' (frequency 1), 'e' (frequency 2). The maximum frequency is 2.
The consonants are: 's' (frequency 4), 'c' (frequency 2). The maximum frequency is 4.
The output is 2 + 4 = 6.

Example 2:

Input: s = "aeiaeia" Output: 3

Explanation:

The vowels are: 'a' (frequency 3), 'e' ( frequency 2), 'i' (frequency 2). The maximum frequency is 3.
There are no consonants in s. Hence, maximum consonant frequency = 0.
The output is 3 + 0 = 3.

Constraints:

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

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:

Is the input string guaranteed to be in a specific case (uppercase, lowercase, or mixed)?
If there's a tie between vowels or consonants for frequency, which one should I return, or should I return both?
What characters besides letters can the input string contain (e.g., spaces, punctuation, numbers)? Should I ignore those?
Is the input string guaranteed to contain at least one vowel and one consonant?
How should I handle an empty input string? Should I return a specific value or throw an exception?

Brute Force Solution

Approach

To find the most frequent vowel and consonant, we'll examine the entire input string piece by piece. We will simply count each vowel and consonant to find the one that appears the most.

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

Start by looking at the input string.
Go through the string, one character at a time.
For each character, check if it is a vowel (a, e, i, o, u). If so, increment the vowel count.
If the character is not a vowel, check if it is a consonant (any letter that is not a vowel). If so, increment the consonant count.
Once you've gone through the entire string, compare the counts of all the vowels.
The vowel with the highest count is the most frequent vowel.
Similarly, compare the counts of all the consonants.
The consonant with the highest count is the most frequent consonant.
Report the most frequent vowel and the most frequent consonant.

Code Implementation

def find_most_frequent_vowel_and_consonant(input_string):
    vowel_counts = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
    consonant_counts = {}

    for character in input_string:
        character = character.lower()

        if 'a' <= character <= 'z':
            if character in vowel_counts:
                vowel_counts[character] += 1

            else:
                # Count the consonants.
                if character in consonant_counts:
                    consonant_counts[character] += 1

                else:
                    consonant_counts[character] = 1

    most_frequent_vowel = None
    max_vowel_count = 0

    for vowel, count in vowel_counts.items():
        if count > max_vowel_count:
            max_vowel_count = count
            most_frequent_vowel = vowel

    most_frequent_consonant = None
    max_consonant_count = 0

    # Only consider consonants if there were any
    if consonant_counts:
        for consonant, count in consonant_counts.items():
            # Ensure higher frequency for consonant.
            if count > max_consonant_count:
                max_consonant_count = count
                most_frequent_consonant = consonant

    return most_frequent_vowel, most_frequent_consonant

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of size n character by character. For each character, a constant number of checks (is it a vowel, is it a consonant) are performed. After the single pass through the string, the algorithm determines the maximum count for vowels and consonants, which takes a constant amount of time. Therefore, the dominant operation is the initial iteration through the string, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of counters to track the frequency of each vowel and consonant. Since the number of vowels and consonants is limited and independent of the input string's length N, the space required for these counters remains constant. No additional data structures that scale with the input size are used. Therefore, the space complexity is O(1).

Optimal Solution

Approach

To find the most frequent vowel and consonant, we'll count how many times each vowel and consonant appears in the input. Then, we'll compare those counts to find the highest one for each category.

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

First, get the input string that we need to analyze.
Next, create separate counters for vowels and consonants. We can use a simple count to keep track.
Go through each character in the string, and change it to lower case to make it case insensitive.
Check if the character is a vowel (a, e, i, o, u). If it is, increment the vowel counter for that specific vowel.
If the character is not a vowel, check if it is a letter of the alphabet. If it is, increment the consonant counter for that specific consonant.
Once you've gone through the entire string, find the vowel with the highest count.
Also find the consonant with the highest count.
Finally, return both the most frequent vowel and the most frequent consonant.

Code Implementation

def find_most_frequent_vowel_and_consonant(input_string):
    vowel_counts = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
    consonant_counts = {}

    for character in input_string:
        lowercase_character = character.lower()

        # Check if the character is a vowel.
        if lowercase_character in vowel_counts:
            vowel_counts[lowercase_character] += 1

        # Check if the character is a consonant.
        elif 'a' <= lowercase_character <= 'z':
            if lowercase_character not in consonant_counts:
                consonant_counts[lowercase_character] = 0
            consonant_counts[lowercase_character] += 1

    most_frequent_vowel = ''
    max_vowel_count = 0

    # Find the vowel with the highest count.
    for vowel, count in vowel_counts.items():
        if count > max_vowel_count:
            max_vowel_count = count
            most_frequent_vowel = vowel

    most_frequent_consonant = ''
    max_consonant_count = 0

    # Find the consonant with the highest count.
    for consonant, count in consonant_counts.items():
        if count > max_consonant_count:
            max_consonant_count = count
            most_frequent_consonant = consonant

    return most_frequent_vowel, most_frequent_consonant

Big(O) Analysis

Time Complexity

O(n) – The dominant operation is iterating through the input string of length n. Inside the loop, we perform a constant number of operations like checking if a character is a vowel or a consonant and incrementing the respective counter. Finding the maximum count vowel and consonant involves iterating through a fixed-size set of vowels and consonants, hence constant time. Therefore, the overall time complexity is determined by the single pass through the string, resulting in O(n).

Space Complexity

O(1) – The solution uses a constant amount of extra space. It creates separate counters for vowels and consonants. Since there are a fixed number of vowels (5) and consonants (21), the space required for these counters remains constant regardless of the input string's length, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty result or null to indicate no frequent characters if input is null or empty.
String with only vowels or only consonants	The solution should correctly identify the most frequent vowel/consonant even if the other category is absent.
String with no vowels or no consonants	Return null for either the most frequent vowel or consonant if it doesn't exist in the input string.
Case sensitivity (uppercase/lowercase letters)	Convert the input string to lowercase before processing to treat 'A' and 'a' as the same character.
Non-alphabetic characters in the input	Ignore or filter out any non-alphabetic characters before counting vowel/consonant frequencies.
Input string with characters from different character sets (e.g., Unicode)	Ensure the vowel and consonant checks correctly handle the expected character sets, potentially requiring Unicode support.
Tie for most frequent vowel or consonant	Return any one of the most frequent characters or define a consistent tie-breaking mechanism (e.g., first occurrence).
Very long input string	Use a character counting approach with O(n) time complexity to ensure efficient performance with large strings.