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

問題

文字列 str を第一引数に、数値 num(str の長さ未満)を第二引数として受け取るJavaScript関数を作成する必要があります。

この関数は、文字列 str の文字を並べ替え、同じ文字同士が少なくとも num 文字以上の間隔で配置された新しい文字列を構築しなければなりません。つまり、同一の文字が互いに近すぎる場所に現れないようにする必要があります。

最終的に、構築した新しい文字列を返します。条件を満たす並べ替えが不可能な場合は、空文字列("")を返してください。

入力例

関数への入力が以下の場合:

const str = 'kkllmm';

期待される出力

const output = 'mlmklk';

解決策

アルゴリズムの考え方

この問題は、以下のステップで解くことができます。

ステップ1:文字の出現回数をカウントする
各文字が何回出現するかをハッシュマップ(オブジェクト)に記録します。

ステップ2:出現回数の降順でキーをソートする
最も多く出現する文字から順に配置できるよう、キーを出現回数の降順に並べ替えます。

ステップ3:実現可能性をチェックする
最頻出文字の個数が「文字列長の半分」(奇数長の場合は切り上げた中央位置)を超えている場合、どのように並べても同じ文字が隣接してしまうため、空文字列を返します。

ステップ4:偶数インデックス → 奇数インデックスの順に配置する
インデックス 0, 2, 4, … と偶数番地から順に文字を埋めていき、末尾に達したら 1, 3, 5, … と奇数番地に切り替えます。この手法により、同じ文字が常に一定以上の間隔を保って配置されます。

コード例

const str = 'kkllmm';
const placeApart = (str = '') => {
    const map = {};
    // ステップ1:各文字の出現回数をカウント
    for(let i=0; i<str.length; i++){
        map[str[i]] = map[str[i]] || 0;
        map[str[i]]++;
    }
    // ステップ2:出現回数の降順でキーをソート
    let keys = Object.keys(map).sort((a,b)=>{
        if(map[a]<map[b])
        return 1;
        return -1;
    });
    // ステップ3:実現可能性の判定
    let len = str.length%2 ? (Math.floor(str.length/2)+1) : str.length/2;
    if(map[keys[0]] > len){
        return "";
    };
    // ステップ4:偶数→奇数インデックスの順に配置
    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(placeApart(str));

計算量について

文字ごとのカウント処理に O(n)、キーのソートに O(k log k)(k は異なる文字の種類数)、配置処理に O(n) を要するため、全体の時間計算量は O(n log n) となります。また、結果を格納する配列とマップのため、空間計算量は O(n) です。

出力結果

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

mlmklk