LeetCode 3541 - Find Most Frequent Vowel and Consonant

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem requires analyzing a string s composed of lowercase English letters and determining the sum of the maximum frequency of vowels and the maximum frequency of consonants. Vowels are defined as 'a', 'e', 'i', 'o', and 'u'. All other letters are consonants. The frequency of a character is the number of times it appears in the string.

The input s represents a sequence of letters, and the output is a single integer: the sum of the highest occurring vowel and the highest occurring consonant. If a string lacks vowels or consonants entirely, the corresponding maximum frequency is considered zero.

Constraints tell us that s is at most length 100, meaning brute-force counting strategies are acceptable. Edge cases to consider include strings that contain only vowels, only consonants, or repeated characters that tie for maximum frequency.

Approaches

The brute-force approach would involve iterating through all letters of the alphabet for each character in the string, counting frequencies separately for vowels and consonants. After counting, we would scan through the counts to find the maximum for vowels and consonants. This approach works correctly but is unnecessary in complexity because we know the string only contains lowercase letters and can be traversed once efficiently.

The optimal approach uses a single pass through the string. For each character, we check if it is a vowel or consonant and update its frequency in the corresponding hash map or array. After processing the entire string, we compute the maximum frequency from each map. This single-pass approach is simple and efficient, leveraging the limited alphabet size.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26 * n)	O(26)	Count each letter for vowels and consonants separately
Optimal	O(n)	O(26)	Single pass, track frequencies in hash maps and compute max

Algorithm Walkthrough

Initialize two dictionaries or arrays, one for vowels and one for consonants, to track the frequency of each letter.
Iterate over each character in the input string.
For each character, check if it is in the set of vowels. If yes, increment its count in the vowel dictionary. Otherwise, increment its count in the consonant dictionary.
After the iteration, compute the maximum frequency for vowels by taking the maximum value in the vowel dictionary. If the dictionary is empty, treat the maximum as zero.
Compute the maximum frequency for consonants in the same way, with zero as a fallback if none exist.
Return the sum of the maximum vowel frequency and the maximum consonant frequency.

Why it works: The algorithm guarantees correct results because it explicitly tracks the frequency of each letter in the string, and maximum frequency is computed from these counts. The invariant is that after the single pass, the dictionaries hold the correct counts for all letters, so selecting the maximum produces the desired frequencies. This problem asks us to analyze a string s composed entirely of lowercase English letters and determine the sum of the maximum frequencies of vowels and consonants. In simpler terms, we need to count how many times each letter occurs, separate vowels from consonants, and then pick the highest count from each category. Finally, we add these two numbers together to get the result.

The input is a string of length between 1 and 100 characters. Each character is guaranteed to be a lowercase English letter. The output is a single integer representing the sum of the highest frequency vowel and the highest frequency consonant.

Important edge cases include strings that contain only vowels or only consonants. In such cases, the frequency for the missing category should be treated as 0. Another potential pitfall is handling multiple vowels or consonants with the same maximum frequency, which the problem allows us to resolve arbitrarily.

Approaches

A brute-force approach would involve iterating over each vowel and consonant separately, counting its occurrences in the string, and keeping track of the maximum. This would be correct but inefficient, as it involves scanning the string repeatedly for each character. With 26 letters, the complexity could become unnecessarily high for larger strings, although the constraints here are small.

The key observation for an optimal solution is that we can scan the string just once, incrementing counters for vowels and consonants as we go. By storing these counts in hash maps (or arrays), we can then simply take the maximum value from each map. This ensures a single linear pass through the string, making the algorithm efficient and straightforward.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26 * n) = O(n)	O(1)	Count each vowel and consonant separately by scanning string multiple times
Optimal	O(n)	O(26) = O(1)	Single pass with hash maps for counts, then find max values

Algorithm Walkthrough

Define a set of vowels {'a', 'e', 'i', 'o', 'u'} to quickly check if a character is a vowel. This allows O(1) membership testing.
Initialize two dictionaries (or hash maps): one for vowel counts and one for consonant counts.
Iterate over each character in the input string s.
For each character, check if it is in the vowel set. If it is, increment its count in the vowel dictionary. Otherwise, increment its count in the consonant dictionary.
After processing the entire string, find the maximum value in the vowel dictionary. If the dictionary is empty, default the maximum to 0.
Similarly, find the maximum value in the consonant dictionary, defaulting to 0 if it is empty.
Return the sum of the maximum vowel frequency and the maximum consonant frequency.

Why it works: Each character is processed exactly once, and the hash maps store accurate counts for every letter. By separately maintaining vowels and consonants, we guarantee that we are computing the correct maximum frequencies for each category.

Python Solution

class Solution:
    def maxFreqSum(self, s: str) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        vowel_count = {}
        consonant_count = {}
        
        for char in s:
            if char in vowels:
                vowel_count[char] = vowel_count.get(char, 0) + 1
            else:
                consonant_count[char] = consonant_count.get(char, 0) + 1
        
        max_vowel_freq = max(vowel_count.values(), default=0)
        max_consonant_freq = max(consonant_count.values(), default=0)
        
        return max_vowel_freq + max_consonant_freq

The implementation first initializes a set for vowels and dictionaries for counting frequencies. As we iterate through each character in the string, we update the corresponding dictionary. The max function with default=0 ensures that strings without vowels or consonants are handled correctly. Finally, the sum of the maximum frequencies is returned. vowels_set = {'a', 'e', 'i', 'o', 'u'} vowel_count = {} consonant_count = {}

    for char in s:
        if char in vowels_set:
            vowel_count[char] = vowel_count.get(char, 0) + 1
        else:
            consonant_count[char] = consonant_count.get(char, 0) + 1

    max_vowel = max(vowel_count.values(), default=0)
    max_consonant = max(consonant_count.values(), default=0)

    return max_vowel + max_consonant


In this implementation, we first define a set of vowels for quick lookup. Two dictionaries keep track of counts for vowels and consonants separately. As we iterate through the string, we increment the corresponding counts. Finally, we compute the maximum frequency for vowels and consonants, defaulting to 0 if a category is missing, and return their sum.

## Go Solution

```go
func maxFreqSum(s string) int {
    vowels := map[rune]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    vowelCount := map[rune]int{}
    consonantCount := map[rune]int{}
    
    vowelCount := make(map[rune]int)
    consonantCount := make(map[rune]int)

    for _, char := range s {
        if vowels[char] {
            vowelCount[char]++
        } else {
            consonantCount[char]++
        }
    }
    
    maxVowel := 0

    maxVowel, maxConsonant := 0, 0
    for _, count := range vowelCount {
        if count > maxVowel {
            maxVowel = count
        }
    }
    
    maxConsonant := 0
    for _, count := range consonantCount {
        if count > maxConsonant {
            maxConsonant = count
        }
    }
    

    return maxVowel + maxConsonant
}

In Go, we use map[rune]bool for vowels and map[rune]int for counting frequencies. The iteration uses a range over the string, which provides each rune. We compute maximum frequencies by iterating over map values. There is no need to handle nil maps explicitly, and integer overflow is not an issue due to the small input size.

Worked Examples

Example 1: s = "successes"

Step	char	vowelCount	consonantCount
1	s	{}	{'s':1}
2	u	{'u':1}	{'s':1}
3	c	{'u':1}	{'s':1,'c':1}
4	c	{'u':1}	{'s':1,'c':2}
5	e	{'u':1,'e':1}	{'s':1,'c':2}
6	s	{'u':1,'e':1}	{'s':2,'c':2}
7	s	{'u':1,'e':1}	{'s':3,'c':2}
8	e	{'u':1,'e':2}	{'s':3,'c':2}
9	s	{'u':1,'e':2}	{'s':4,'c':2}

Maximum vowel frequency = 2, maximum consonant frequency = 4, sum = 6

Example 2: s = "aeiaeia"

Step	char	vowelCount	consonantCount
Iteration over characters	update vowelCount	{'a':3,'e':2,'i':2}	{}

Maximum vowel frequency = 3, maximum consonant frequency = 0, sum = 3 In Go, we use a map of runes to booleans to store vowels, and two maps for counts. Iterating over the string with range ensures each rune is processed correctly. Maximum values are computed manually since Go does not provide a built-in max for map values.

Worked Examples

Example 1: s = "successes"

Character	Type	Vowel Count	Consonant Count
s	C	{}	{'s': 1}
u	V	{'u': 1}	{'s': 1}
c	C	{'u': 1}	{'s': 1, 'c': 1}
c	C	{'u': 1}	{'s': 1, 'c': 2}
e	V	{'u': 1, 'e': 1}	{'s': 1, 'c': 2}
s	C	{'u': 1, 'e': 1}	{'s': 2, 'c': 2}
s	C	{'u': 1, 'e': 1}	{'s': 3, 'c': 2}
e	V	{'u': 1, 'e': 2}	{'s': 3, 'c': 2}
s	C	{'u': 1, 'e': 2}	{'s': 4, 'c': 2}

Maximum vowel frequency = 2 (e), maximum consonant frequency = 4 (s). Sum = 6.

Example 2: s = "aeiaeia"

Character	Type	Vowel Count	Consonant Count
a	V	{'a': 1}	{}
e	V	{'a': 1, 'e': 1}	{}
i	V	{'a': 1, 'e': 1, 'i': 1}	{}
a	V	{'a': 2, 'e': 1, 'i': 1}	{}
e	V	{'a': 2, 'e': 2, 'i': 1}	{}
i	V	{'a': 2, 'e': 2, 'i': 2}	{}
a	V	{'a': 3, 'e': 2, 'i': 2}	{}

Maximum vowel frequency = 3 (a), maximum consonant frequency = 0 (no consonants). Sum = 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over the string of length n, updating counts
Space	O(26)	Fixed-size storage for vowels and consonants, at most 26 keys each

The time complexity is linear because we process each character exactly once. Space complexity is constant because the alphabet size is fixed, so maps or arrays never grow beyond 26 entries. | Time | O(n) | Single pass through the string to count letters, where n = length of s | | Space | O(26) = O(1) | Hash maps store counts for at most 26 letters each |

Even though we use hash maps, the size is bounded by the fixed alphabet size, so space is effectively constant.

Test Cases

# Provided examples
assert Solution().maxFreqSum("successes") == 6  # mixed vowels and consonants
assert Solution().maxFreqSum("aeiaeia") == 3   # only vowels
assert Solution().maxFreqSum("bcd") == 3       # only consonants

# Additional cases
assert Solution().maxFreqSum("a") == 1         # single vowel
assert Solution().maxFreqSum("z") == 1         # single consonant
assert Solution().maxFreqSum("aaaaaaa") == 7   # repeated vowel only
assert Solution().maxFreqSum("bcdfg") == 1     # all consonants, max frequency 1
assert Solution().maxFreqSum("aeiou") == 1     # all vowels, max frequency 1
assert Solution().maxFreqSum("abcdeiou") == 2  # mixed, max vowel=1, max consonant=1
assert Solution().maxFreqSum("aeiaeia") == 3    # only vowels

# Boundary cases
assert Solution().maxFreqSum("a") == 1          # single vowel
assert Solution().maxFreqSum("b") == 1          # single consonant
assert Solution().maxFreqSum("aaabbb") == 4     # tie among vowels and consonants

# Edge cases
assert Solution().maxFreqSum("bcdfgh") == 1     # no vowels
assert Solution().maxFreqSum("aeiou") == 1      # no consonants
assert Solution().maxFreqSum("ababab") == 3     # alternating vowels and consonants

Test	Why
"successes"	mixed letters, verifies correct counting and sum
"aeiaeia"	no consonants, verifies vowel handling with zero fallback
"bcd"	no vowels, verifies consonant handling with zero fallback
"a" / "z"	minimal length, single letter edge cases
"aaaaaaa"	repeated letters, ensure counting correctly
"bcdfg"	multiple consonants with same frequency
"aeiou"	multiple vowels, all same frequency
"abcdeiou"	mix of vowels and consonants, ensures correct max selection

Edge Cases

The first edge case is when the string contains only vowels, such as "aeiouaeiou". The algorithm correctly returns the maximum vowel frequency, and the consonant maximum is zero. A naive approach might attempt to find consonants and throw an error if none exist, but our use of default=0 handles this gracefully.

The second edge case occurs when the string contains only consonants, such as "bcdfg". Similar to the first case, the maximum vowel frequency is zero, and our algorithm handles this without special branching.