Если да, то я не понимаю как быстрее чем за N * log N сделать, не то что за N. Надо ж сортировать так или иначе. Ну можно, наверное, какой-то бакет сорт прикрутить, но мне лень: взял обычный heap. Зато чистенько.
https://leetcode.com/discuss/general-discussion/645121/Sort-Characters-By-Frequency