JavaScriptで同じ文字どうしがn文字離れるように文字列を並べ替える方法

問題の概要

繰り返し登場する文字を含む文字列と整数 n を引数として受け取り、すべての同じ文字が互いにちょうど n 文字離れて配置されるような新しい文字列を返す JavaScript 関数を実装します。なお、n は元の文字列の長さよりも小さい値である必要があります。

たとえば、次のようになります。

入力文字列: "accessories"
n = 3 の場合
期待される戻り値: "secrsecisao"

注意: 条件を満たす並べ替え方は複数存在します。文字の並び順そのものは重要ではなく、「同じ文字が n 文字間隔で配置される」というロジックを満たしていれば、どの出力でも正解として扱われます。

アプローチの考え方

この問題は、次の手順で解くことができます。

• まず Map を使って、各文字が出現する回数を集計します。
• 出現回数の降順で文字を並べ替えます。出現頻度の高い文字から先に配置することで、間隔の制約を満たしやすくなります。
• インデックス i を n で割った余り(i % n)を基準に、ラウンドロビン方式で文字を配置していきます。これにより、同じ文字が常に n 文字間隔で配置されるようになります。

実装例

const str = 'accessories';
const equalDistance = (str, num) => {
    const map = str.split("").reduce((acc, val) => {
        const count = acc.get(val);
        if(typeof count === 'number'){
            acc.set(val, count+1);
        }else{
            acc.set(val, 1);
        };
        return acc;
    }, new Map());
    const arr = Array.from(map).sort((a, b) => b[1] - a[1]);
    let newString = '';
    for(let i = 0, count = 0; i < str.length;){
        if(!arr[count][1]){
            arr.splice(count, 1);
            continue;
        };
        newString += arr[count][0];
        arr[count][1]--;
        i++;
        count = i % num;
    };
    return newString;
};
console.log(equalDistance(str, 4));
console.log(equalDistance('abb', 2));
console.log(equalDistance('aacbbc', 3));

コードのポイント

reduce() と Map を組み合わせて各文字の出現回数を効率的にカウントし、Array.from(map) で「文字と出現回数」のペア配列に変換した後、出現回数の降順にソートしています。ループ処理の中では、残り出現回数が 0 になった文字を splice() で配列から取り除きながら、count = i % num という計算によって n 文字間隔の配置を実現しています。

出力結果

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

sceasceosri
bab
acbacb

このように、各文字が指定された間隔(n)ごとに正しく配置された文字列が得られます。「accessories」の場合、s は 0・4・8 番目に、c は 1・5 番目に配置されており、それぞれが n 文字ずつ離れていることが確認できます。