# Find Most Frequent Vowel and Consonant
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-most-frequent-vowel-and-consonant)
Canonical: https://scaleengineer.com/dsa/problems/find-most-frequent-vowel-and-consonant
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force with Nested Loops
This approach iterates through every letter of the alphabet. For each letter, it scans the entire input string to count its occurrences. Based on whether the letter is a vowel or a consonant, it updates the respective maximum frequency.
**Time:** O(26 * N) or simply O(N), where N is the length of the string. The outer loop runs a constant 26 times, and for each iteration, the inner loop runs N times. · **Space:** O(1), as we only use a few variables to store the maximum frequencies and loop counters.
**Pros:** Simple to understand and implement without complex data structures.; Uses constant extra space.
**Cons:** Highly inefficient due to repeated scanning of the input string.; The time complexity has a large constant factor (26), making it slower than single-pass approaches for the same O(N) classification.
### Explanation
The brute-force method directly tackles the problem by checking the frequency of every possible character. It involves a loop that runs 26 times (for each letter 'a' through 'z'). Inside this loop, another loop iterates through the input string `s` to count how many times the current letter appears. After counting, it checks if the letter is a vowel or a consonant and updates the corresponding maximum frequency found so far. While straightforward, this method is inefficient because it re-scans the input string 26 times.

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public int findMostFrequentVowelAndConsonant(String s) {
        int maxVowelFreq = 0;
        int maxConsonantFreq = 0;

        for (char c = 'a'; c <= 'z'; c++) {
            int currentFreq = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == c) {
                    currentFreq++;
                }
            }

            if (currentFreq > 0) {
                if (isVowel(c)) {
                    maxVowelFreq = Math.max(maxVowelFreq, currentFreq);
                } else {
                    maxConsonantFreq = Math.max(maxConsonantFreq, currentFreq);
                }
            }
        }
        return maxVowelFreq + maxConsonantFreq;
    }
}
```
### Algorithm
- Initialize `maxVowelFreq` and `maxConsonantFreq` to 0.
- Create a helper function or a set to identify vowels.
- Iterate through each character `c` of the alphabet from 'a' to 'z'.
- For each character `c`, initialize a `currentFreq` counter to 0.
- Start a nested loop to iterate through the input string `s`.
- If a character in `s` matches `c`, increment `currentFreq`.
- After the inner loop finishes, check if `c` is a vowel.
- If `c` is a vowel, update `maxVowelFreq = Math.max(maxVowelFreq, currentFreq)`.
- If `c` is a consonant, update `maxConsonantFreq = Math.max(maxConsonantFreq, currentFreq)`.
- After iterating through the entire alphabet, return `maxVowelFreq + maxConsonantFreq`.

## Single Pass with HashMap
This approach improves upon the brute-force method by first counting the frequencies of all characters in a single pass and storing them in a HashMap. Then, it iterates through the map's entries to find the maximum vowel and consonant frequencies.
**Time:** O(N), where N is the length of the string. We iterate through the string once to build the map (O(N)) and then iterate through the unique characters in the map (O(K), where K <= 26). · **Space:** O(K), where K is the number of unique characters in the string. Since the input is limited to lowercase English letters, K is at most 26, making the space complexity effectively O(1).
**Pros:** Much more efficient than the nested loop approach as the string is traversed only once.; Flexible and works for any character set, not just lowercase English letters.
**Cons:** Has a slight overhead associated with HashMap operations (hashing, potential collisions) compared to a simple array.; Uses more memory than a fixed-size array, although both are O(1) in this specific problem context.
### Explanation
A more efficient way to solve the problem is to first count the frequencies of all characters present in the string and then process these frequencies. We can iterate through the string `s` just once, using a HashMap to store each character and its corresponding count. After populating the map, we iterate through its entries. For each character, we determine if it's a vowel or a consonant and update the respective maximum frequency. This avoids the repeated scanning of the input string.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

class Solution {
    public int findMostFrequentVowelAndConsonant(String s) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        int maxVowelFreq = 0;
        int maxConsonantFreq = 0;
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');

        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            char c = entry.getKey();
            int freq = entry.getValue();
            if (vowels.contains(c)) {
                maxVowelFreq = Math.max(maxVowelFreq, freq);
            } else {
                maxConsonantFreq = Math.max(maxConsonantFreq, freq);
            }
        }
        return maxVowelFreq + maxConsonantFreq;
    }
}
```
### Algorithm
- Create a `HashMap<Character, Integer>` to store character frequencies.
- Iterate through the input string `s` once. For each character, update its count in the HashMap.
- Initialize `maxVowelFreq` and `maxConsonantFreq` to 0.
- Define a set of vowels for O(1) lookup.
- Iterate through the key-value pairs (entries) in the HashMap.
- For each entry `(character, frequency)`:
  - If the character is a vowel, update `maxVowelFreq = Math.max(maxVowelFreq, frequency)`.
  - Otherwise, it's a consonant, so update `maxConsonantFreq = Math.max(maxConsonantFreq, frequency)`.
- Return the sum `maxVowelFreq + maxConsonantFreq`.

## Optimal Single Pass with Frequency Array
This is the most efficient approach. Since the input consists only of lowercase English letters, we can use a fixed-size array of 26 elements to store character frequencies. This avoids the overhead of a HashMap and provides the fastest performance due to direct memory access.
**Time:** O(N), where N is the length of the string. The first loop to populate the array is O(N), and the second loop to find max frequencies is O(26), which is constant time. The overall complexity is dominated by the first loop. · **Space:** O(1), as the frequency array has a constant size of 26.
**Pros:** Most efficient in terms of both time and space due to direct array indexing and minimal overhead.; Very simple and clean implementation.
**Cons:** This approach is specifically tailored to a fixed, small character set (like lowercase English letters). It is less flexible than a HashMap if the character set were unknown or very large.
### Explanation
The optimal solution leverages the constraint that the input string only contains lowercase English letters. Instead of a HashMap, we can use a simple integer array of size 26 as a frequency map. The index `0` of the array corresponds to 'a', `1` to 'b', and so on. We make a single pass over the string to populate this frequency array. Then, we make a second, constant-time pass (26 iterations) over the frequency array itself to find the maximum frequencies for vowels and consonants.

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public int findMostFrequentVowelAndConsonant(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        int maxVowelFreq = 0;
        int maxConsonantFreq = 0;

        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                char c = (char) ('a' + i);
                if (isVowel(c)) {
                    maxVowelFreq = Math.max(maxVowelFreq, freq[i]);
                } else {
                    maxConsonantFreq = Math.max(maxConsonantFreq, freq[i]);
                }
            }
        }
        return maxVowelFreq + maxConsonantFreq;
    }
}
```
### Algorithm
- Create an integer array `freq` of size 26, initialized to all zeros.
- Iterate through the input string `s`. For each character `c`, increment the count at the corresponding index: `freq[c - 'a']++`.
- Initialize `maxVowelFreq` and `maxConsonantFreq` to 0.
- Iterate through the `freq` array from index `i = 0` to `25`.
- For each index `i`, get the corresponding character `ch = (char)('a' + i)`.
- Check if `ch` is a vowel.
- If it is a vowel, update `maxVowelFreq = Math.max(maxVowelFreq, freq[i])`.
- If it is a consonant, update `maxConsonantFreq = Math.max(maxConsonantFreq, freq[i])`.
- Return the sum `maxVowelFreq + maxConsonantFreq`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def maxFreqSum(self, s: str) -> int: cnt = Counter(s) a = b = 0 for c, v in cnt . items(): if c in "aeiou": a = max(a, v) else: b = max(b, v) return a + b

```