Find Most Frequent Vowel and Consonant

Difficulty: Easy | Acceptance: 89.30% | Paid: No Topics: Hash Table, String, Counting

You are given a string s consisting of lowercase English letters. A letter is a vowel if it is in the set {'a', 'e', 'i', 'o', 'u'}. Otherwise, it is a consonant.

Return a list of two strings: the most frequent vowel and the most frequent consonant.

If there are multiple vowels with the same maximum frequency, return the lexicographically smallest one. If there are multiple consonants with the same maximum frequency, return the lexicographically smallest one.

If there are no vowels in the string, return an empty string "" for the vowel part. If there are no consonants in the string, return an empty string "" for the consonant part.

• Examples
• Constraints
• Approach 1: Hash Map Counting
• Approach 2: Fixed Array Counting

Examples

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 <= 10⁵
s consists of lowercase English letters.

Approach 1: Hash Map Counting

Intuition We can iterate through the string and separate the characters into two groups: vowels and consonants. We use a hash map (or dictionary) to count the frequency of characters in each group. Finally, we iterate through the maps to find the character with the highest frequency, breaking ties by selecting the lexicographically smallest character.

Steps

• Initialize two hash maps: one for vowels and one for consonants.
• Iterate through each character in the string s.
• Check if the character is a vowel.
• If it is a vowel, increment its count in the vowel map. Otherwise, increment its count in the consonant map.
• After processing the string, determine the most frequent vowel by iterating through the vowel map. Track the maximum frequency and the corresponding character. If frequencies are equal, choose the smaller character.
• Repeat the process for the consonant map.
• Return the results as a list. If a map is empty, return an empty string for that part.

class Solution:
    def mostFrequentVowelAndConsonant(self, s: str) -> list[str]:
        vowels = set('aeiou')
        v_count = {}
        c_count = {}
        
        for char in s:
            if char in vowels:
                v_count[char] = v_count.get(char, 0) + 1
            else:
                c_count[char] = c_count.get(char, 0) + 1
        
        def get_most_frequent(count_map):
            if not count_map:
                return ""
            max_char = ""
            max_freq = -1
            for char, freq in count_map.items():
                if freq > max_freq or (freq == max_freq and char < max_char):
                    max_freq = freq
                    max_char = char
            return max_char
        
        return [get_most_frequent(v_count), get_most_frequent(c_count)]

Complexity

• Time: O(n) where n is the length of the string. We iterate through the string once and then through the unique characters (at most 26).
• Space: O(1) because the number of distinct characters is bounded by the alphabet size (26), regardless of the input string length.
• Notes: Hash maps provide O(1) average time complexity for insertions and lookups.

Approach 2: Fixed Array Counting

Intuition Since the input consists only of lowercase English letters, we can optimize space and speed by using fixed-size arrays of length 26 instead of hash maps. We map each character to an index (e.g., ‘a’ -> 0, ‘b’ -> 1). This avoids the overhead of hashing and is generally faster for small, fixed key sets.

Steps

• Create two integer arrays of size 26: vCount and cCount, initialized to 0.
• Iterate through the string s.
• For each character, calculate its index (e.g., char.charCodeAt(0) - 'a'.charCodeAt(0)).
• Check if the character is a vowel.
• If it is a vowel, increment vCount[index]. Otherwise, increment cCount[index].
• Iterate through the vCount array (indices 0 to 25) to find the index with the maximum value. If values are equal, pick the smaller index (which corresponds to the lexicographically smaller character). Convert the index back to the character.
• Repeat the process for cCount.
• Return the results.

class Solution:
    def mostFrequentVowelAndConsonant(self, s: str) -> list[str]:
        vowels = set('aeiou')
        v_count = [0] * 26
        c_count = [0] * 26
        
        for char in s:
            idx = ord(char) - ord('a')
            if char in vowels:
                v_count[idx] += 1
            else:
                c_count[idx] += 1
        
        def get_most_frequent(count_arr):
            max_freq = -1
            max_idx = -1
            for i in range(26):
                if count_arr[i] > 0:
                    if count_arr[i] > max_freq or (count_arr[i] == max_freq and i < max_idx):
                        max_freq = count_arr[i]
                        max_idx = i
            if max_idx == -1:
                return ""
            return chr(max_idx + ord('a'))
        
        return [get_most_frequent(v_count), get_most_frequent(c_count)]

Complexity

• Time: O(n) where n is the length of the string. We iterate through the string once and then through the fixed-size array of 26 elements.
• Space: O(1) because we use two fixed-size arrays of length 26, which does not depend on the input size.
• Notes: This approach is generally more performant than hash maps due to lower overhead and better cache locality, though the difference is negligible for this specific problem size.