Character Frequency Sorting — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(k+n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Character Frequency Sorting problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(k+n)

Problem Description

Given a string s, compute how many times each distinct character appears. Produce a new string that lists all characters of s sorted primarily by decreasing frequency. When two characters share the same frequency, the one with the lower ASCII code precedes the other. Each character must appear in the result exactly as many times as it occurs in the original string. The algorithm should run efficiently for strings up to 10^5 characters.

DSA Pattern Breakdown

"Character Frequency Sorting"

medium

WHY DOES IT MATTER?

Frequency‑based ordering appears in compression (Huffman coding), load‑balancing logs, and UI ranking where the most common items must be highlighted first; mastering this pattern teaches you to convert counting problems into linear‑time sorts.

OPTIMIZATION CHALLENGE

The key insight is that the range of possible frequencies (0…n) is small relative to n, enabling a counting‑sort style bucket array where each bucket holds characters sharing that frequency, thus avoiding generic comparison‑based sorting.

REAL-WORLD CONNECTION

Think of a warehouse where items are restocked based on demand frequency; you bucket items by demand levels and process the highest‑demand bucket first, analogous to bucket‑sorting characters by occurrence count.

When coding, first build a fixed‑size frequency array, then create a vector of vectors sized (n+1) for buckets; fill them, and finally iterate from n down to 1, appending characters in ASCII order—this pattern is both fast and easy to debug.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k+n)

Core Theory — Why This Approach?

The problem reduces to counting frequencies of each character and then ordering them by a composite key: descending frequency then ascending ASCII. A naïve solution would sort the original string repeatedly or use nested loops to count each character, leading to O(n^2) time for large inputs, which quickly becomes infeasible for strings of length up to 10^5 or more. The optimal paradigm leverages a linear pass to build a frequency map (often an array of size 256 for ASCII or a hash map for Unicode) and then a bucket‑sort or counting‑sort style arrangement because frequencies are bounded by the string length, allowing O(n) sorting without comparison overhead.

By placing characters into buckets indexed by their frequency, we can iterate frequencies from high to low and emit characters in ASCII order within each bucket. This eliminates the O(k log k) cost of sorting a list of distinct characters (where k ≤ 256) and guarantees linear time overall. The approach also respects the stability requirement—each character appears exactly as many times as in the input—while using only O(k + n) auxiliary space, which is optimal for this class of problems.

Interview Questions on This Problem

Q1How would you modify the solution if the input string could contain Unicode characters beyond the basic ASCII range?

Use a hash map (e.g., unordered_map<char32_t,int>) to count frequencies instead of a fixed‑size array, and then bucket‑sort based on the maximum frequency observed; the rest of the algorithm remains unchanged.

Q2At a fintech firm you need to return the sorted string in O(n) time but memory is limited to O(1) extra space besides the output. What technique can you apply?

Perform an in‑place counting sort by first counting frequencies in a fixed‑size array (constant space for Unicode code‑points if bounded) and then overwrite the original string sequentially from highest frequency to lowest, emitting each character its count times.

Q3Why might a candidate choose to sort the distinct characters with a custom comparator instead of bucket sort, and why is that sub‑optimal for large inputs?

A custom comparator sorts k distinct characters in O(k log k) time; while k is small for ASCII, it becomes noticeable for larger alphabets or when the constant factors matter, whereas bucket sort runs in O(n + maxFreq) which is linear and avoids the log factor entirely.

Examples

Example 1

Input

tree

Output

eert

Explanation: The character frequencies are: e→2, r→1, t→1. Sorting by frequency gives e first. r and t have equal frequency, and 'r' (ASCII 114) is smaller than 't' (ASCII 116), so r precedes t. The result is e repeated twice followed by r and t: eert.

Example 2

Input

Aabb

Output

bbAa

Explanation: Frequencies: A→1, a→1, b→2. The highest frequency is 2 for 'b', so 'b' appears first twice. The remaining characters have frequency 1; 'A' (ASCII 65) is smaller than 'a' (ASCII 97), therefore 'A' comes before 'a'. Result: bbAa.

Example 3

Input

cccbbba

Output

bbbccca

Explanation: Frequencies: c→3, b→3, a→1. Both 'b' and 'c' have the same highest frequency (3). Since 'b' (ASCII 98) < 'c' (ASCII 99), 'b' is placed before 'c'. After listing three 'b's and three 'c's, the single 'a' is appended, yielding bbbccca.

Constraints

1 <= s.length <= 100000
All characters in s are printable ASCII (code 32 to 126)
The solution should run in O(n log n) time or better, where n is the length of s

Optimal Approach & Strategy

Use a single pass to build a frequency map, then bucket‑sort frequencies and emit characters from highest to lowest, achieving O(n) time.

Brute Force Approach

Count each character by scanning the string for every possible character, resulting in O(n × k) time where k is the alphabet size.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function frequencySort(s) {
    const freq = new Array(256).fill(0);
    for (let i = 0; i < s.length; i++) freq[s.charCodeAt(i)]++;
    const arr = [];
    for (let i = 0; i < 256; i++) if (freq[i]) arr.push({ch: i, cnt: freq[i]});
    arr.sort((a, b) => {
        if (b.cnt !== a.cnt) return b.cnt - a.cnt;
        return a.ch - b.ch;
    });
    let res = '';
    for (const {ch, cnt} of arr) {
        res += String.fromCharCode(ch).repeat(cnt);
    }
    return res;
}

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trimEnd();
if (input !== undefined) console.log(frequencySort(input));

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

string frequencySort(const string& s) {
    vector<int> cnt(256, 0);
    for (unsigned char c : s) cnt[c]++;
    vector<pair<int, char>> vec;
    for (int i = 0; i < 256; ++i) if (cnt[i]) vec.push_back({cnt[i], static_cast<char>(i)});
    sort(vec.begin(), vec.end(), [](const pair<int,char>& a, const pair<int,char>& b){
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    string res;
    for (auto &p : vec) res.append(p.first, p.second);
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (getline(cin, s)) cout << frequencySort(s);
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static String frequencySort(String s) {
        int[] cnt = new int[256];
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i)]++;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < 256; i++) if (cnt[i] > 0) list.add(new int[]{i, cnt[i]});
        list.sort((a, b) -> {
            if (b[1] != a[1]) return b[1] - a[1];
            return a[0] - b[0];
        });
        StringBuilder sb = new StringBuilder();
        for (int[] p : list) {
            for (int i = 0; i < p[1]; i++) sb.append((char) p[0]);
        }
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        System.out.print(frequencySort(s));
    }
}

from collections import Counter

def frequency_sort(s: str) -> str:
    cnt = Counter(s)
    items = sorted(cnt.items(), key=lambda x: (-x[1], ord(x[0])))
    return ''.join(ch * freq for ch, freq in items)

if __name__ == "__main__":
    import sys
    s = sys.stdin.read().rstrip('\n')
    print(frequency_sort(s))

function frequencySort(s) {
    const freq = new Array(256).fill(0);
    for (let i = 0; i < s.length; i++) freq[s.charCodeAt(i)]++;
    const arr = [];
    for (let i = 0; i < 256; i++) if (freq[i]) arr.push({ch: i, cnt: freq[i]});
    arr.sort((a, b) => {
        if (b.cnt !== a.cnt) return b.cnt - a.cnt;
        return a.ch - b.ch;
    });
    let res = '';
    for (const {ch, cnt} of arr) {
        res += String.fromCharCode(ch).repeat(cnt);
    }
    return res;
}

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trimEnd();
if (input !== undefined) console.log(frequencySort(input));

Asked in Top Tech Interviews

PayPal

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.