JavaScriptで同じ文字が隣接しないように文字列を並べ替える方法

JavaScriptで、文字列を第一引数（唯一の引数）として受け取る関数を作成することを考えます。

この関数の役割は、文字列に含まれる各文字を並べ替え、同一の文字が隣り合わないように再配置することです。

そのような組み合わせが少なくとも1つ存在する場合は、結果となる文字列を返します。もし条件を満たす並べ方が存在しない場合は、空文字列（""）を返します。

具体的な例を見てみましょう。入力文字列が次の場合：

const str = 'add';

関数の出力は次のようになります：

const output = 'dad';

アルゴリズムの考え方

この問題を解くポイントは以下の通りです。

• まず各文字の出現回数をハッシュマップでカウントします。
• 文字を出現頻度の高い順にソートします。
• 最も多く出現する文字が、文字列長の半分（奇数長の場合は切り上げて＋1）より多い場合、どのように並べ替えても同じ文字が隣接してしまうため、空文字列を返します。
• それ以外の場合は、頻度の高い文字から順に偶数インデックス（0, 2, 4...）へ配置していきます。偶数インデックスを使い切ったら、今度は奇数インデックス（1, 3, 5...）に戻って配置を続けます。

この手法により、頻度の高い文字同士が隣接するのを効率的に防ぐことができます。

コード例

以下が実際のコードです。

const str = 'add';
const formatString = (str = '') => {
    const map = {};
    // 各文字の出現回数をカウント
    for(let i = 0; i < str.length; i++){
        map[str[i]] = map[str[i]] || 0;
        map[str[i]] ++;
    }
    // 出現頻度の降順でキーをソート
    let keys = Object.keys(map).sort((a, b) => {
        if(map[a] < map[b]){
            return 1;
        };
        return -1;
    });
    // 同一文字が隣接不可になる閾値を計算
    let flag = str.length%2?(Math.floor(str.length/2)+1):str.length/2;
    if(map[keys[0]] > flag){
        return "";
    };
    const res = [];
    let index = 0, max = str.length-1;
    while(keys.length){
        let currKey = keys.shift();
        let count = map[currKey];
        while(count){
            res[index] = currKey;
            index = index+2;
            if(index>max)
                index=1;
            count--;
        }
    }
    return res.join("");
};
console.log(formatString(str));

処理の流れ

1. 文字列を走査し、各文字の出現回数をオブジェクト map に記録します。
2. キー一覧を出現回数の降順にソートします。
3. 最頻出文字の個数が許容上限（文字列長の半分・奇数なら切り上げ＋1）を超えていないかチェックし、超えていれば空文字列を返します。
4. 結果配列 res の偶数インデックスに文字を順番に埋め込み、末尾に達したら奇数インデックス（index = 1）に移動して残りの文字を配置します。
5. 最後に配列を結合して文字列として返します。

出力

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

dad

このように、「a」の間に「d」が挟まれる形で、同一文字の隣接が回避された文字列が得られます。