Majority Frequency Characters solution and explanation
6 more videos on this problem
Majority Frequency Characters | LeetCode 3692 | Biweekly Contest 166Sanyam IIT Guwahati · 9:18 · 377 views
3692. Majority Frequency Characters (Leetcode Easy)Programming Live with Larry · 8:59 · 262 views
Biweekly Contest 166 Solution | Leetcode 3692 | Majority Frequency CharactersSamrat Bhardwaj · 12:12 · 203 views
LeetCode 3692 🔥 Majority Frequency Characters | Biweekly Contest 166 | Optimal Solution + Dry Run Study Placement · 9:02 · 184 views
Leetcode 3692 Majority Frequency CharactersAlgorithmicIQ · 13:28 · 89 views
Majority Frequency Characters | Biweekly Contest 166 | Leetcode 3692ExpertFunda · 28:59 · 81 views
Day 780: LeetCode Problem 3692. Majority Frequency Characters - SwiftiOSxBank · 10:59 · 28 views
The problem
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 <= 100sconsists 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.
class Solution:
def majorityFrequencyGroup(self, s: str) -> str:
cnt = Counter(s)
f = defaultdict(list)
for c, v in cnt.items():
f[v].append(c)
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
return "".join(ans)class Solution {
public String majorityFrequencyGroup(String s) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) {
++cnt[c - 'a'];
}
Map<Integer, StringBuilder> f = new HashMap<>();
for (int i = 0; i < cnt.length; ++i) {
if (cnt[i] > 0) {
f.computeIfAbsent(cnt[i], k -> new StringBuilder()).append((char) ('a' + i));
}
}
int mx = 0;
int mv = 0;
String ans = "";
for (var e : f.entrySet()) {
int v = e.getKey();
var cs = e.getValue();
if (mx < cs.length() || (mx == cs.length() && mv < v)) {
mx = cs.length();
mv = v;
ans = cs.toString();
}
}
return ans;
}
}class Solution {
public:
string majorityFrequencyGroup(string s) {
vector<int> cnt(26, 0);
for (char c : s) {
++cnt[c - 'a'];
}
unordered_map<int, string> f;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
f[cnt[i]].push_back('a' + i);
}
}
int mx = 0, mv = 0;
string ans;
for (auto& e : f) {
int v = e.first;
string& cs = e.second;
if (mx < (int) cs.size() || (mx == (int) cs.size() && mv < v)) {
mx = cs.size();
mv = v;
ans = cs;
}
}
return ans;
}
};function majorityFrequencyGroup(s: string): string {
const cnt: Record<string, number> = {};
for (const c of s) {
cnt[c] = (cnt[c] || 0) + 1;
}
const f = new Map<number, string[]>();
for (const [c, v] of Object.entries(cnt)) {
if (!f.has(v)) {
f.set(v, []);
}
f.get(v)!.push(c);
}
let [mx, mv] = [0, 0];
let ans = '';
f.forEach((cs, v) => {
if (mx < cs.length || (mx == cs.length && mv < v)) {
mx = cs.length;
mv = v;
ans = cs.join('');
}
});
return ans;
}func majorityFrequencyGroup(s string) string {
cnt := make([]int, 26)
for _, c := range s {
cnt[c-'a']++
}
f := make(map[int][]byte)
for i, v := range cnt {
if v > 0 {
f[v] = append(f[v], byte('a'+i))
}
}
mx, mv := 0, 0
var ans []byte
for v, cs := range f {
if len(cs) > mx || (len(cs) == mx && v > mv) {
mx = len(cs)
mv = v
ans = cs
}
}
return string(ans)
}Complexity analysis
| 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 |
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.
