3692. Majority Frequency Characters

Easy

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s made up of lowercase English letters.

First, count how many times each character appears in s. Characters that appear exactly the same number of times belong to the same frequency group. In other words, the frequency group for a value k is the set of all distinct characters that appear exactly k times in s.

Among all frequency groups, the majority frequency group is the one that contains the most distinct characters.

Your task is to return a string containing every character in the majority frequency group. The characters can appear in any order.

Tie-breaking rule: if two or more frequency groups have the same (largest) number of distinct characters, choose the group whose frequency value k is larger.

For example, if s = "aaabbbccdd":

a appears 3 times, b appears 3 times — so the group for k = 3 is {a, b} with 2 distinct characters.
c appears 2 times, d appears 2 times — so the group for k = 2 is {c, d} with 2 distinct characters.

Both groups contain 2 distinct characters, so we pick the group with the larger frequency, which is k = 3. The answer is "ab" (or "ba", since order does not matter).

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Counting character frequencies and grouping them by frequency value is a two-layer hash table problem.

Open in Flowchart

Intuition

The problem naturally breaks into two layers of counting:

How many times does each character appear? This is a classic frequency count, so a hash table (or Counter) immediately comes to mind — it maps each character to its count.
Which characters share the same frequency? Once we know each character's count, grouping characters by that count is just another mapping: this time the key is the frequency k and the value is the list of characters appearing exactly k times. This is exactly what "frequency group" means in the problem, translated directly into a data structure.

After building these two maps, the answer is simply the group with the largest list. So we scan through all groups while keeping track of the best one seen so far, using two pieces of state:

mx: the size (number of distinct characters) of the best group so far.
mv: the frequency value k of the best group so far.

A new group replaces the current best in two situations, mirroring the problem's rules:

Its size is strictly larger than mx (it has more distinct characters), or
Its size equals mx but its frequency k is larger than mv (the tie-breaking rule).

Because every character appears in exactly one frequency group, one pass over the groups is enough — there's no need for sorting or anything more elaborate. The whole solution is just "count, group, then pick the best group in a single scan," which runs in linear time relative to the length of s.

Solution Approach

Hash Table

The implementation follows three clear steps: count → group → select.

Step 1: Count character frequencies.

Use a hash table cnt to record how many times each character appears in s:

cnt = Counter(s)

After this step, cnt[c] gives the frequency of character c. For example, with s = "aaabbcc", we get cnt = {'a': 3, 'b': 2, 'c': 2}.

Step 2: Group characters by frequency.

Build a second hash table f, where the key is a frequency value k and the value is the list of characters that appear exactly k times:

f = defaultdict(list)
for c, v in cnt.items():
    f[v].append(c)

Continuing the example, f = {3: ['a'], 2: ['b', 'c']}. Each list f[k] is precisely the frequency group for k.

Step 3: Pick the majority frequency group in one scan.

Iterate over all (v, cs) pairs in f, where v is the frequency and cs is its character list. Maintain:

mx — the largest group size found so far,
mv — the frequency of that group,
ans — the character list of that group.

Update the best answer when the current group is strictly larger, or equal in size but with a larger frequency:

mx = mv = 0
ans = []
for v, cs in f.items():
    if mx < len(cs) or (mx == len(cs) and mv < v):
        mx = len(cs)
        mv = v
        ans = cs

The condition mx < len(cs) or (mx == len(cs) and mv < v) encodes both the "largest group wins" rule and the "larger k breaks ties" rule in a single check.

Finally, join the winning group's characters into a string:

return "".join(ans)

For s = "aaabbcc", group k = 2 has size 2 and group k = 3 has size 1, so the answer is "bc".

Complexity Analysis

Time complexity: O(n + |Σ|), where n is the length of s and |Σ| = 26 is the alphabet size. Counting takes O(n); grouping and scanning touch at most 26 distinct characters and 26 distinct frequencies.
Space complexity: O(|Σ|), since both hash tables store at most 26 entries in total.

Example Walkthrough

Let's trace the algorithm with s = "aabbcd".

Step 1: Count character frequencies.

Scanning the string and building the counter:

cnt = {'a': 2, 'b': 2, 'c': 1, 'd': 1}

So a and b each appear twice, while c and d each appear once.

Step 2: Group characters by frequency.

Invert the mapping so that each frequency points to the characters sharing it:

Character `c`	Count `v`	Action	`f` after the action
`'a'`	2	append to `f[2]`	`{2: ['a']}`
`'b'`	2	append to `f[2]`	`{2: ['a', 'b']}`
`'c'`	1	append to `f[1]`	`{2: ['a', 'b'], 1: ['c']}`
`'d'`	1	append to `f[1]`	`{2: ['a', 'b'], 1: ['c', 'd']}`

We end up with two frequency groups: k = 2 → {a, b} and k = 1 → {c, d}, each containing 2 distinct characters.

Step 3: Scan the groups to pick the winner.

Start with mx = 0, mv = 0, ans = [].

Group `(v, cs)`	Check `mx < len(cs) or (mx == len(cs) and mv < v)`	Result	State after
`(2, ['a', 'b'])`	`0 < 2` → true	update	`mx = 2`, `mv = 2`, `ans = ['a', 'b']`
`(1, ['c', 'd'])`	`2 < 2` is false; `2 == 2 and 2 < 1` is false → false	skip	unchanged

Notice how the second group triggers the tie-breaking logic: it matches the best size (2), but its frequency 1 is not larger than the current best frequency 2, so the existing answer is kept. This is exactly the rule "if group sizes tie, prefer the larger k."

Final step: Build the result.

"".join(['a', 'b']) → "ab"

The algorithm returns "ab" — the group of characters appearing 2 times wins the tie over the group appearing 1 time, and the whole process took just one pass to count, one pass to group, and one pass to select.

Solution Implementation

1from collections import Counter, defaultdict
2
3
4class Solution:
5    def majorityFrequencyGroup(self, s: str) -> str:
6        # Count the occurrences of each character in the string
7        char_count = Counter(s)
8
9        # Group characters by their frequency:
10        # key -> frequency, value -> list of characters having that frequency
11        freq_groups = defaultdict(list)
12        for char, freq in char_count.items():
13            freq_groups[freq].append(char)
14
15        # Track the best group found so far:
16        # max_group_size -> the largest number of characters in a group
17        # max_freq       -> the frequency associated with that group
18        max_group_size = max_freq = 0
19        ans = []
20
21        # Iterate over all frequency groups to find the majority group.
22        # A group wins if it contains more characters,
23        # or (on a tie in size) if its frequency is higher.
24        for freq, chars in freq_groups.items():
25            group_size = len(chars)
26            if max_group_size < group_size or (
27                max_group_size == group_size and max_freq < freq
28            ):
29                max_group_size = group_size
30                max_freq = freq
31                ans = chars
32
33        # Concatenate the characters of the winning group into a string
34        return "".join(ans)
35

1class Solution {
2    public String majorityFrequencyGroup(String s) {
3        // Count the occurrences of each lowercase letter in the string
4        int[] count = new int[26];
5        for (char ch : s.toCharArray()) {
6            ++count[ch - 'a'];
7        }
8
9        // Group characters by their frequency:
10        // key   -> frequency value
11        // value -> all characters that appear exactly that many times
12        Map<Integer, StringBuilder> frequencyGroups = new HashMap<>();
13        for (int i = 0; i < count.length; ++i) {
14            if (count[i] > 0) {
15                frequencyGroups
16                    .computeIfAbsent(count[i], k -> new StringBuilder())
17                    .append((char) ('a' + i));
18            }
19        }
20
21        // Track the best group found so far:
22        // maxGroupSize -> the largest number of characters in a group
23        // maxFrequency -> the frequency value of that group (tie-breaker)
24        int maxGroupSize = 0;
25        int maxFrequency = 0;
26        String answer = "";
27
28        // Iterate over all frequency groups to find the majority group
29        for (Map.Entry<Integer, StringBuilder> entry : frequencyGroups.entrySet()) {
30            int frequency = entry.getKey();
31            StringBuilder group = entry.getValue();
32
33            // Choose this group if it contains more characters,
34            // or if it ties in size but has a higher frequency
35            if (maxGroupSize < group.length()
36                    || (maxGroupSize == group.length() && maxFrequency < frequency)) {
37                maxGroupSize = group.length();
38                maxFrequency = frequency;
39                answer = group.toString();
40            }
41        }
42
43        return answer;
44    }
45}
46

1class Solution {
2public:
3    string majorityFrequencyGroup(string s) {
4        // Count the occurrences of each lowercase letter
5        vector<int> count(26, 0);
6        for (char ch : s) {
7            ++count[ch - 'a'];
8        }
9
10        // Group characters by their frequency:
11        // key   -> frequency value
12        // value -> string of all characters having that frequency
13        unordered_map<int, string> frequencyGroups;
14        for (int i = 0; i < 26; ++i) {
15            if (count[i] > 0) {
16                frequencyGroups[count[i]].push_back('a' + i);
17            }
18        }
19
20        // Find the group with the largest size;
21        // if sizes tie, prefer the group with the higher frequency
22        int maxGroupSize = 0;   // size of the largest group found so far
23        int maxFrequency = 0;   // frequency value of that group
24        string ans;
25        for (auto& entry : frequencyGroups) {
26            int frequency = entry.first;
27            string& group = entry.second;
28            int groupSize = static_cast<int>(group.size());
29            if (maxGroupSize < groupSize ||
30                (maxGroupSize == groupSize && maxFrequency < frequency)) {
31                maxGroupSize = groupSize;
32                maxFrequency = frequency;
33                ans = group;
34            }
35        }
36        return ans;
37    }
38};
39

1function majorityFrequencyGroup(s: string): string {
2    // Step 1: Count the occurrences of each character in the string.
3    const charCount: Record<string, number> = {};
4    for (const ch of s) {
5        charCount[ch] = (charCount[ch] || 0) + 1;
6    }
7
8    // Step 2: Group characters by their frequency.
9    // Key: frequency value, Value: list of characters having that frequency.
10    const frequencyGroups = new Map<number, string[]>();
11    for (const [ch, freq] of Object.entries(charCount)) {
12        if (!frequencyGroups.has(freq)) {
13            frequencyGroups.set(freq, []);
14        }
15        frequencyGroups.get(freq)!.push(ch);
16    }
17
18    // Step 3: Find the group with the largest size.
19    // If two groups have the same size, prefer the one with the higher frequency.
20    let maxGroupSize = 0;   // Size of the largest frequency group found so far
21    let maxFrequency = 0;   // Frequency value of the chosen group
22    let result = '';        // Characters belonging to the chosen group
23
24    frequencyGroups.forEach((chars, freq) => {
25        const groupSize = chars.length;
26        if (
27            maxGroupSize < groupSize ||
28            (maxGroupSize === groupSize && maxFrequency < freq)
29        ) {
30            maxGroupSize = groupSize;
31            maxFrequency = freq;
32            result = chars.join('');
33        }
34    });
35
36    // Step 4: Return the concatenated characters of the majority frequency group.
37    return result;
38}
39

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.
- Building the counter cnt = Counter(s) takes O(n) time, as it iterates over every character in s.
- Constructing the frequency-group map f iterates over the entries of cnt. Since there are at most min(n, 26) distinct characters, this step takes O(min(n, 26)) time, which is bounded by O(n).
- The final loop iterates over the groups in f, which is also bounded by the number of distinct characters, taking O(min(n, 26)) time.
- Joining the answer list with "".join(ans) takes at most O(26) time.
- Overall, the dominant cost is the initial counting pass, giving a total of O(n).
Space Complexity: O(n) in general, where n is the length of the string s.
- The counter cnt and the map f together store at most min(n, 26) distinct characters and their frequencies.
- The answer list ans holds at most 26 characters.
- Strictly speaking, since the character set is limited to lowercase letters, the extra space is bounded by a constant (O(26), i.e., O(1)); under a general alphabet assumption, it is O(n).

Common Pitfalls

Pitfall 1: Confusing "group size" with "frequency value" when comparing groups

The most frequent mistake is selecting the group whose frequency k is largest (or whose characters appear the most times) instead of the group with the most distinct characters. The word "majority" tempts people into comparing the wrong quantity.

Buggy example:

# WRONG: picks the group with the highest frequency value,
# not the group with the most distinct characters
best_freq = max(freq_groups.keys())
return "".join(freq_groups[best_freq])

For s = "abbccc", this returns "c" (frequency 3), but the correct answer is "a"... actually each group {a}, {b}, {c} has size 1, so the tie-break picks k = 3 → "c" here. A clearer failing case is s = "aabbc": groups are {a, b} (size 2, k = 2) and {c} (size 1, k = 1). The buggy code returns "ab" by luck only if 2 > 1; flip it to s = "aabccc" and it returns "c" while the correct answer is "ab" (group {a, b} at k = 1... here a appears 2, b appears 1, c appears 3 — each group has size 1, tie-break gives "c"). The reliable counterexample is:

s = "aabbccc" → groups: k = 2 → {a, b} (size 2), k = 3 → {c} (size 1).
Correct answer: "ab". Buggy code returns "c".

Fix: Always compare len(chars) first, and only use the frequency k as a tie-breaker:

if max_group_size < group_size or (
    max_group_size == group_size and max_freq < freq
):
    ...

Pitfall 2: Getting the tie-breaking direction wrong (or omitting it)

A subtle variant of the bug above: comparing sizes correctly but breaking ties with the smaller frequency, or relying on dictionary iteration order and skipping the tie-break entirely.

Buggy example:

# WRONG: keeps the first group seen on ties,
# which depends on insertion order, not on the larger k
if group_size > max_group_size:
    max_group_size = group_size
    ans = chars

For s = "aaabbbccdd", both k = 3 → {a, b} and k = 2 → {c, d} have size 2. Depending on which group is encountered first, this code may return "cd" instead of the required "ab".

Fix: Make the tie-break explicit with max_freq < freq, so a group only replaces the current best when it is strictly larger in size or equal in size with a strictly larger frequency. An equivalent one-liner that avoids manual bookkeeping entirely:

return "".join(
    max(freq_groups.items(), key=lambda kv: (len(kv[1]), kv[0]))[1]
)

Here the key (len(chars), freq) encodes both rules: group size dominates, and frequency breaks ties.

Pitfall 3: Counting duplicate characters instead of distinct characters in a group

Some attempts measure a group's "size" as k * number_of_chars (total occurrences) or accidentally append the same character multiple times by iterating over s instead of cnt.items() when building freq_groups.

Buggy example:

# WRONG: iterating over s adds 'a' three times to group 3 for s = "aaab"
for c in s:
    freq_groups[char_count[c]].append(c)

This inflates group sizes (group 3 becomes ['a', 'a', 'a'] with length 3) and also produces an output string with repeated characters.

Fix: Build the groups from the frequency map's items, which guarantees each distinct character is added exactly once:

for char, freq in char_count.items():
    freq_groups[freq].append(char)

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

3692. Majority Frequency Characters

Problem Description

How We Pick the Algorithm

Why Hash Table / Counting?

Intuition

Solution Approach

Hash Table

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Confusing "group size" with "frequency value" when comparing groups

Pitfall 2: Getting the tie-breaking direction wrong (or omitting it)

Pitfall 3: Counting duplicate characters instead of distinct characters in a group

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings