JavaScriptで複数の文字列に共通する文字を重複込みで抽出する方法

問題

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

この関数の役割は、配列内のすべての文字列に出現する文字を抽出し、それらを配列として返すことです。重複も含めて扱う必要がある点に注意してください。

たとえば、ある文字がすべての文字列の中で2回ずつ出現している場合（3回ではない場合）、最終的な結果にもその文字を2回だけ含めます。

入力と出力の例

たとえば、関数への入力が次のような場合を考えてみましょう。

const arr = ['door', 'floor', 'crook'];

'r' は3つの文字列すべてに1回ずつ現れ、'o' は 'door' に2回、'floor' に2回、'crook' に2回現れているため、出力は次のようになります。

const output = ['r', 'o', 'o'];

解決策：サンプルコード

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

const arr = ['door', 'floor', 'crook'];
const findCommon = (arr = []) => {
    let prev = null;
    arr.forEach((str) => {
        const next = {};
        for(const val of str){
            if(!prev){
                next[val] = (next[val] || 0) + 1;
            }else if(prev[val]){
                prev[val] -= 1;
                next[val] = (next[val] || 0) + 1;
            };
        };
        prev = next;
    });
    const res = Object.keys(prev).reduce((acc, val) => {
        for(let i = 0; i < prev[val]; i++){
            acc.push(val);
        }
        return acc
    }, []);
    return res;
};
console.log(findCommon(arr));

出力

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

[ 'r', 'o', 'o' ]

アルゴリズムの解説

このコードでは、各文字の「出現回数」をオブジェクトで管理しながら処理を進めます。具体的な流れは次のとおりです。

最初の文字列については、各文字の出現回数をそのままカウントします。2つ目以降の文字列に対しては、前の文字列までで確定した共通カウント（prev）を参照し、その文字がまだ残っている場合にのみカウントを引き継ぎます。これにより、各文字列間で「共通して存在する分だけ」の回数が保持されます。

最後に、reduce() を使ってカウントオブジェクトを配列に展開すれば、重複を含んだ共通文字の配列が完成します。

計算量は文字列の総文字数に比例するため、O(n) の効率で動作し、文字列の数や長さが増えても実用的な速度で処理できます。