3541: Find Most Frequent Vowel and Consonant

Difficulty: Easy

Topics: String Manipulation, Frequency Counting

Companies: Amazon, Microsoft, Bloomberg

Pro Tip: The optimal solution requires efficient frequency counting and proper classification of vowels vs consonants.

Problem Statement

Given a string, return the sum of maximum vowel frequency and maximum consonant frequency. Handle edge cases where no vowels/consonants exist.

Example 1

Input: s = "successes"
Output: 6
Explanation: Max vowel (e) = 2, Max consonant (s) = 4

Example 2

Input: s = "aeiaeia"
Output: 3
Explanation: Max vowel (a) = 3, No consonants

Problem Link: View on LeetCode ↗

Approach 1: Frequency Array (Optimal)

Use fixed-size array to store character frequencies for O(1) lookups.

Algorithm Steps

Initialize 26-element frequency array
Count character occurrences
Iterate through alphabet to find max frequencies

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(1)

Optimal Solution

class Solution {
public:
    int maxFreqSum(string s) {
        vector<int> freq(26, 0);
        for(char c : s) freq[c-'a']++;
        
        int max_vowel = 0, max_cons = 0;
        for(int i = 0; i < 26; ++i) {
            char c = 'a' + i;
            if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                max_vowel = max(max_vowel, freq[i]);
            } else {
                max_cons = max(max_cons, freq[i]);
            }
        }
        return max_vowel + max_cons;
    }
};

class Solution {
    public int maxFreqSum(String s) {
        int[] freq = new int[26];
        for(char c : s.toCharArray()) freq[c-'a']++;
        
        int maxVowel = 0, maxCons = 0;
        for(int i = 0; i < 26; i++) {
            char c = (char)('a' + i);
            if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                maxVowel = Math.max(maxVowel, freq[i]);
            } else {
                maxCons = Math.max(maxCons, freq[i]);
            }
        }
        return maxVowel + maxCons;
    }
}

class Solution:
    def maxFreqSum(self, s: str) -> int:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
            
        max_vowel = max_cons = 0
        for i in range(26):
            c = chr(ord('a') + i)
            if c in {'a', 'e', 'i', 'o', 'u'}:
                max_vowel = max(max_vowel, freq[i])
            else:
                max_cons = max(max_cons, freq[i])
        return max_vowel + max_cons

Implementation Note: This method provides constant space complexity and optimal performance for all input sizes.

Approach 2: Hash Map (Alternative)

Use dictionary-based frequency counting for better readability.

Algorithm Steps

Create frequency map using hash table
Iterate through map entries
Track maximum frequencies during iteration

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(26)

Alternative Solution

class Solution {
public:
    int maxFreqSum(string s) {
        unordered_map<char, int> freq;
        for(char c : s) freq[c]++;
        
        int max_vowel = 0, max_cons = 0;
        for(auto& [c, count] : freq) {
            if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                max_vowel = max(max_vowel, count);
            } else {
                max_cons = max(max_cons, count);
            }
        }
        return max_vowel + max_cons;
    }
};

class Solution {
    public int maxFreqSum(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for(char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        
        int maxVowel = 0, maxCons = 0;
        for(Map.Entry<Character, Integer> entry : freq.entrySet()) {
            char c = entry.getKey();
            if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                maxVowel = Math.max(maxVowel, entry.getValue());
            } else {
                maxCons = Math.max(maxCons, entry.getValue());
            }
        }
        return maxVowel + maxCons;
    }
}

class Solution:
    def maxFreqSum(self, s: str) -> int:
        freq = {}
        for c in s:
            freq[c] = freq.get(c, 0) + 1
            
        max_vowel = max_cons = 0
        for c, count in freq.items():
            if c in {'a', 'e', 'i', 'o', 'u'}:
                max_vowel = max(max_vowel, count)
            else:
                max_cons = max(max_cons, count)
        return max_vowel + max_cons

Implementation Note: While theoretically similar in complexity, this method has slightly higher constant factors due to hash table operations.

Approach Comparison

Approach	Time	Space	Best Use Case
Frequency Array	O(n)	O(1)	Optimal for fixed character sets
Hash Map	O(n)	O(26)	More readable code

Important: Both approaches have same asymptotic complexity but array method is generally faster in practice due to direct memory access.

Edge Case Analysis

1. All Vowels

Input: "aeiou" → Output: 1 + 0 = 1

2. Single Character

Input: "z" → Output: 0 + 1 = 1

3. Mixed Case with Ties

Input: "abcde" → vowels (a,e) max=1, consonants (b,c,d) max=1 → Output: 2

Warning: Always check for empty vowel/consonant groups and handle zero cases properly.

Frequently Asked Questions

1. Why use 26-element array instead of hash map?

Direct indexing provides O(1) access time and better cache locality, making it more efficient for fixed character sets.

2. How to handle uppercase letters?

Convert to lowercase first using tolower() or similar functions before processing.

3. What if the string contains non-alphabetic characters?

Problem constraints guarantee only lowercase letters, so no special handling needed.

4. Can we optimize further by tracking max during counting?

No, because we need complete frequency data to determine global maximums.

5. Why check character type during second pass?

Separates vowel/consonant logic from counting phase, keeping code modular and clean.

6. How to extend for uppercase letters?

Normalize case: freq[c.lower()]++ and adjust character checks accordingly.

7. What's the maximum possible sum?

When all characters are same vowel/consonant: sum = n (string length).

8. How to verify solution correctness?

Manually calculate frequencies for small strings and compare with output.

9. Can we use bit manipulation?

Not practical for this problem - frequency counting is more straightforward.

10. Real-world applications?

Text analysis, cryptography, and natural language processing tasks.

Final Insight: This problem demonstrates fundamental frequency counting techniques crucial for string manipulation problems. While simple, it teaches important concepts in efficient data organization.