Welcome to Subscribe On Youtube

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}$.

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


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


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

All Problems

All Solutions