JavaScriptで文字列を出現頻度の高い順に並べ替える方法

問題

文字列を唯一の引数として受け取るJavaScript関数を作成します。

この関数は、元の文字列をもとに新しい文字列を生成し、出現回数が最も多い文字を先頭に配置し、以降は出現頻度の高い順（降順）に残りの文字を並べる必要があります。

たとえば、関数への入力が次の場合：

const str = 'free';

出力は次のようになります。

const output = 'eefr';

出力の解説

eは2回出現するため先頭に配置され、その後に出現回数が1回ずつのfとrが続きます。

サンプルコード

この問題を解くコードは以下の通りです。

const str = 'free';

const frequencySort = (str = '') => {
    let map = {}
    for (const letter of str) {
        map[letter] = (map[letter] || 0) + 1;
    };
    let res = "";
    let sorted = Object.keys(map).sort((a, b) => map[b] - map[a])
    for (let letter of sorted) {
        for (let count = 0; count < map[letter]; count++) {
            res += letter
        }
    }
    return res;
};
console.log(frequencySort(str));

コードの解説

このコードでは、以下の3つのステップで処理を行っています。

• ステップ1： まず、各文字の出現回数を記録するハッシュマップ（オブジェクト）を作成します。

• ステップ2： 次に、Object.keys()で取得した文字のキーを、出現回数に基づいて降順にソートします。

• ステップ3： 最後に、ソート済みの文字をもとに、各文字を出現回数分だけ繰り返し連結して結果文字列resを組み立て、返却します。

なお、このアルゴリズムの計算量は、文字列の長さをnとするとO(n log n)になります。文字の集計にO(n)、ソートにO(k log k)（kはユニークな文字の種類数）を要するため、効率的な実装と言えます。

出力

コンソールには次のように表示されます。

eefr