Find Most Frequent Vowel and Consonant
EasyPrompt
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 letterx 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 <= 100sconsists of lowercase English letters only.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
maxVowelFreqandmaxConsonantFreqto 0. - Create a helper function or a set to identify vowels.
- Iterate through each character
cof the alphabet from 'a' to 'z'. - For each character
c, initialize acurrentFreqcounter to 0. - Start a nested loop to iterate through the input string
s. - If a character in
smatchesc, incrementcurrentFreq. - After the inner loop finishes, check if
cis a vowel. - If
cis a vowel, updatemaxVowelFreq = Math.max(maxVowelFreq, currentFreq). - If
cis a consonant, updatemaxConsonantFreq = Math.max(maxConsonantFreq, currentFreq). - After iterating through the entire alphabet, return
maxVowelFreq + maxConsonantFreq.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a
HashMap<Character, Integer>to store character frequencies. - Iterate through the input string
sonce. For each character, update its count in the HashMap. - Initialize
maxVowelFreqandmaxConsonantFreqto 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).
- If the character is a vowel, update
- Return the sum
maxVowelFreq + maxConsonantFreq.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Create an integer array
freqof size 26, initialized to all zeros. - Iterate through the input string
s. For each characterc, increment the count at the corresponding index:freq[c - 'a']++. - Initialize
maxVowelFreqandmaxConsonantFreqto 0. - Iterate through the
freqarray from indexi = 0to25. - For each index
i, get the corresponding characterch = (char)('a' + i). - Check if
chis 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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 + bVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.