Watch 7 video solutions for Majority Frequency Characters, a easy level problem involving Hash Table, String, Counting. This walkthrough by Sanyam IIT Guwahati has 342 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100s consists only of lowercase English letters.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Counting | O(n²) | O(1) | Useful for understanding the baseline approach or when input size is extremely small |
| Hash Table Frequency Count | O(n) | O(k) | Best general solution for strings where frequency tracking is required |