Skip to main content
Talentd

Majority Frequency Characters - Solution & Explanation

EasyHash TableStringCounting8 min read
Practice this problem

Problem Statement

You are given a string s consisting of lowercase English letters.

The frequency group for a value k is the set of characters that appear exactly k times in s.

The majority frequency group is the frequency group that contains the largest number of distinct characters.

Return a string containing all characters in the majority frequency group, in any order. If two or more frequency groups tie for that largest size, pick the group whose frequency k is larger.

 

Example 1:

Input: s = "aaabbbccdddde"

Output: "ab"

Explanation:

Frequency (k) Distinct characters in group Group size Majority?
4 {d} 1 No
3 {a, b} 2 Yes
2 {c} 1 No
1 {e} 1 No

Both characters 'a' and 'b' share the same frequency 3, they are in the majority frequency group. "ba" is also a valid answer.

Example 2:

Input: s = "abcd"

Output: "abcd"

Explanation:

Frequency (k) Distinct characters in group Group size Majority?
1 {a, b, c, d} 4 Yes

All characters share the same frequency 1, they are all in the majority frequency group.

Example 3:

Input: s = "pfpfgi"

Output: "fp"

Explanation:

Frequency (k) Distinct characters in group Group size Majority?
2 {p, f} 2 Yes
1 {g, i} 2 No (tied size, lower frequency)

Both characters 'p' and 'f' share the same frequency 2, they are in the majority frequency group. There is a tie in group size with frequency 1, but we pick the higher frequency: 2.

 

Constraints:

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

Approach Overview

Problem Overview: You are given a string and need to identify the character(s) that appear with the highest frequency. If multiple characters share the same maximum count, all of them should be returned.

Approach 1: Brute Force Counting (O(n²) time, O(1) space)

Check the frequency of every character by scanning the entire string for each position. For each index i, iterate through the string again and count how many times s[i] appears. Track the maximum frequency encountered and maintain a list of characters that match it. Because each character triggers a full scan of the string, the total time complexity becomes O(n²). Extra space stays O(1) if you only track counts using simple variables. This method works for small inputs but becomes inefficient as the string length grows.

Approach 2: Hash Table Frequency Count (O(n) time, O(k) space)

Use a frequency map to count occurrences in a single pass. Iterate through the string and store counts in a hash map where the key is the character and the value is its frequency. After building the map, iterate through its entries to determine the maximum frequency and collect characters whose counts match that value. Each character is processed once during counting and once during evaluation, giving a total time complexity of O(n). Space complexity is O(k), where k is the number of unique characters.

This approach relies on constant‑time average lookup and update operations provided by a hash table. The string is traversed sequentially, which aligns well with common string processing patterns. The frequency counting step is also a classic application of counting techniques used in many interview problems.

Recommended for interviews: The hash table counting approach is the expected solution. It demonstrates understanding of frequency maps and reduces the complexity from O(n²) to O(n). Mentioning the brute force method first shows awareness of the naive baseline, but implementing the single-pass counting solution proves you can optimize using the right data structure.

Solution

We first use an array or hash table cnt to count the frequency of each character in the string. Then, we use another hash table f to group characters with the same frequency k into the same list, i.e., f[k] stores all characters with frequency k.

Next, we iterate through the hash table f to find the frequency group with the maximum group size. If multiple frequency groups have the same maximum size, we choose the one with the larger frequency k. Finally, we concatenate all characters in that frequency group into a string and return it.

The time complexity is O(n) and the space complexity is O(n), where n is the length of string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force CountingO(n²)O(1)Useful for understanding the baseline approach or when input size is extremely small
Hash Table Frequency CountO(n)O(k)Best general solution for strings where frequency tracking is required

Video Solution

Majority Frequency Characters | LeetCode 3692 | Biweekly Contest 166 • Sanyam IIT Guwahati • 377 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Majority Frequency Characters easy or hard?
Majority Frequency Characters is generally considered an easy problem. The core idea is straightforward frequency counting with a hash map, a common pattern in string and array interview questions.
Majority Frequency Characters Python/Java solution
Most implementations follow the same pattern: build a frequency map, compute the maximum frequency, then collect matching characters. In Python you typically use a dictionary or collections.Counter, while Java implementations use HashMap<Character, Integer>.
How to solve Majority Frequency Characters in O(n)?
Traverse the string and store character counts in a hash map. Track the highest frequency while scanning the map or in a second pass. Any character whose count equals the maximum frequency belongs in the result set. Because each character is processed a constant number of times, the total runtime stays O(n).
What is the best approach for Majority Frequency Characters?
The best approach uses a hash table to count the frequency of each character in the string. After one pass to build the frequency map, a second pass identifies the maximum count and collects all characters with that frequency. This method runs in O(n) time and O(k) space, where k is the number of unique characters.
Is Majority Frequency Characters asked at Google/Amazon/Meta?
Frequency counting problems on strings are common in interviews at companies like Google, Amazon, and Meta. Variants often involve finding the most frequent character, top‑k frequent elements, or majority elements using hash maps or counting arrays.
What data structure is used in Majority Frequency Characters?
The main data structure is a hash table (hash map) that maps characters to their occurrence counts. It allows constant‑time average updates and lookups, making it ideal for frequency counting tasks.
What is the time complexity of Majority Frequency Characters?
The optimal solution runs in O(n) time. You iterate through the string once to build a frequency map and once more to determine the maximum frequency. Space complexity is O(k) for storing counts of unique characters.

Ready to solve this problem?

Practice Majority Frequency Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters