Majority Frequency Characters

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

Given a string s, return the character that appears more than n / 2 times, where n is the length of the string. If no such character exists, return an empty string.

You may assume that the string is non-empty and contains only lowercase English letters.

• Examples
• Constraints
• Hash Map Counting
• Sorting
• Boyer-Moore Voting Algorithm

Examples

Example 1

Input: s = "aaaabc"
Output: "a"
Explanation: The length of the string is 6. The character 'a' appears 4 times, which is greater than 6 / 2 = 3.

Example 2

Input: s = "abc"
Output: ""
Explanation: The length of the string is 3. No character appears more than 1.5 times.

Example 3

Input: s = "bba"
Output: "b"
Explanation: The length of the string is 3. The character 'b' appears 2 times, which is greater than 3 / 2 = 1.5.

Constraints

- 1 <= s.length <= 100
- s consists only of lowercase English letters.

Hash Map Counting

Intuition We can iterate through the string and count the frequency of each character using a hash map. After counting, we check which character has a frequency greater than n / 2.

Steps

• Initialize an empty hash map (or dictionary) to store character counts.
• Iterate through each character in the string s.
• For each character, increment its count in the hash map.
• After the loop, iterate through the hash map entries.
• If any character’s count is greater than s.length / 2, return that character.
• If no such character is found after checking all entries, return an empty string.

from collections import Counter

class Solution:
    def majorityFrequencyCharacters(self, s: str) -> str:
        n = len(s)
        counts = Counter(s)
        
        for char, count in counts.items():
            if count > n // 2:
                return char
                
        return ""

Complexity

• Time: O(n) - We iterate through the string once to count and once through the map (which has at most 26 entries for lowercase English letters, so effectively O(n)).
• Space: O(1) - The hash map stores at most 26 entries (constant space relative to input size). If the character set were unlimited, it would be O(n).
• Notes: This is the most intuitive approach and works well for the given constraints.

Sorting

Intuition If a character appears more than n / 2 times, it must occupy the middle position(s) in the sorted string. We can sort the string and check the character at the middle index.

Steps

• Convert the string to a character array (if necessary for the language).
• Sort the character array.
• The candidate for the majority element is the character at index n / 2.
• Iterate through the string to count the frequency of this candidate character.
• If the count is greater than n / 2, return the candidate.
• Otherwise, return an empty string.

class Solution:
    def majorityFrequencyCharacters(self, s: str) -> str:
        n = len(s)
        sorted_s = sorted(s)
        candidate = sorted_s[n // 2]
        
        count = 0
        for char in s:
            if char == candidate:
                count += 1
                
        if count > n // 2:
            return candidate
        return ""

Complexity

• Time: O(n log n) - Due to the sorting step.
• Space: O(n) or O(log n) - Depending on the sorting implementation and whether we modify the string in place.
• Notes: While simple, sorting is slower than linear time approaches.

Boyer-Moore Voting Algorithm

Intuition The Boyer-Moore Voting Algorithm finds a majority element in a sequence (if it exists) in linear time and constant space. It maintains a count and a candidate. When the count drops to zero, we pick a new candidate.

Steps

• Initialize candidate as an empty character and count as 0.
• Iterate through the string s:
  • If count is 0, set candidate to the current character.
  • If the current character is equal to candidate, increment count.
  • Otherwise, decrement count.
• After the loop, candidate holds the potential majority element.
• Iterate through the string again to verify if candidate actually appears more than n / 2 times.
• Return candidate if verified, otherwise return an empty string.

class Solution:
    def majorityFrequencyCharacters(self, s: str) -> str:
        candidate = ''
        count = 0
        
        for char in s:
            if count == 0:
                candidate = char
                count = 1
            elif char == candidate:
                count += 1
            else:
                count -= 1
        
        # Verification step
        count = 0
        for char in s:
            if char == candidate:
                count += 1
                
        if count > len(s) // 2:
            return candidate
        return ""

Complexity

• Time: O(n) - Two passes through the string.
• Space: O(1) - Only using a few variables for storage.
• Notes: This is the optimal solution for space complexity, though for a fixed character set like lowercase English letters, the Hash Map approach is effectively O(1) space as well and often easier to implement.