3692. Majority Frequency Characters

Description

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.

Solutions

Solution: Hash Table

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

Next, we iterate through the hash table \(\textit{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 \(\textit{s}\).

Python3JavaC++GoTypeScript

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;
    }
};

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)
}

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;
}

3692. Majority Frequency Characters

Description

Solutions

Solution: Hash Table

Comments