Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

Sort Characters by Frequency

Medium · Strings · Asked at Amazon, Google, Bloomberg, Zoho

Rearrange the characters so that more frequent characters come first; all copies of a character stay together. If two characters have the same frequency, the one with the smaller ASCII code comes first.

Input

A single string s of letters and digits.

Output

The rearranged string.

Constraints

Count frequencies, then sort the distinct characters by (frequency desc, character asc). Bucket sort by frequency is O(n).

Example 1

Input

tree

Output

eert

Example 2

Input

cccaaa

Output

aaaccc

Hints

  1. Count how often each character occurs.
  2. Sort the distinct characters by (count descending, character ascending) and print each one count times.

Approach

Count with an array of 128 (ASCII). Collect the characters that occur, sort them with the comparator "higher count first, then smaller character", and append each character count times. Only up to 62 distinct characters are sorted, so the sort is tiny; the overall cost is dominated by reading and writing the string.

Complexity: O(n + k log k) time · O(n) space (k = distinct characters)

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    vector<int> cnt(128, 0);
    for (char c : s) cnt[c]++;
    vector<char> chars;
    for (int c = 0; c < 128; c++)
        if (cnt[c]) chars.push_back((char)c);
    sort(chars.begin(), chars.end(), [&](char a, char b) {
        if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
        return a < b;
    });
    string out;
    for (char c : chars) out += string(cnt[c], c);
    cout << out << "\n";
    return 0;
}

Python solution

from collections import Counter

s = input().strip()
cnt = Counter(s)
order = sorted(cnt, key=lambda c: (-cnt[c], c))
print("".join(c * cnt[c] for c in order))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String s = new Scanner(System.in).next();
        int[] cnt = new int[128];
        for (char c : s.toCharArray()) cnt[c]++;
        List<Character> chars = new ArrayList<>();
        for (int c = 0; c < 128; c++)
            if (cnt[c] > 0) chars.add((char) c);
        chars.sort((a, b) -> cnt[a] != cnt[b] ? cnt[b] - cnt[a] : a - b);
        StringBuilder out = new StringBuilder();
        for (char c : chars) out.append(String.valueOf(c).repeat(cnt[c]));
        System.out.println(out);
    }
}

Solve Sort Characters by Frequency online · All practice problems