JavaScriptで共通文字を持たない2つの単語の最大長の積を求める方法

問題

小文字の英字のみで構成された文字列の配列を、最初かつ唯一の引数として受け取るJavaScript関数を作成する必要があります。

この関数の役割は、配列の中から共通する文字を1つも持たない2つの文字列を選び出し、それらの長さの積が最大になる組み合わせを見つけることです。そして、その積を戻り値として返します。該当する組み合わせが1つも存在しない場合は、0を返してください。

入力例

const arr = ["karl", "n", "the", "car", "mint", "alpha"];

期待される出力

const output = 20;

出力の説明

「mint」（4文字）と「alpha」（5文字）は、互いに共通する文字を1つも持ちません。したがって、その長さの積は4 × 5 = 20となり、これが最大値となります。

解法のポイント：ビットマスクによる高速化

すべての文字列ペアに対して文字の一致を毎回調べるのは非効率です。そこで有効なのが、各文字列を26ビットの整数（ビットマスク）に変換する手法です。

• 英小文字「a」〜「z」を、それぞれ0〜25の番号に対応させます。
• 文字列内の各文字について、1 << (charCodeAt(i) - 97)で対応するビットを立て、OR演算（|=）で蓄積していきます。
• こうして作った2つのビットマスクの論理積（AND）が0になれば、その2つの文字列は共通する文字を持たないことを意味します。

事前にビットマスクへ変換しておけば、ペア同士の比較は定数時間のビット演算だけで済むため、処理全体を大幅に高速化できます。

サンプルコード

const arr = ["karl", "n", "the", "car", "mint", "alpha"];
const maxLengthProduct = (arr = []) => {
    const array = [];
    // 各文字列を26ビットのビットマスクに変換
    arr.forEach(str => {
        let curr = 0;
        for(let i = 0; i < str.length; i++){
            curr |= 1<<(str.charCodeAt(i) - 97);
        };
        array.push(curr);
    });
    let res = 0;
    // 全ペアを比較し、共通文字なし（AND = 0）なら積を更新
    for(let i = 0 ; i < array.length; i++) {
        for(let j = i + 1; j < array.length ; j++) {
            if((array[i] & array[j]) === 0) {
                res = Math.max(res, arr[i].length * arr[j].length);
            }
        }
    }
    return res;
};
console.log(maxLengthProduct(arr));

実行結果

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

20

まとめ

本アルゴリズムでは、前処理（全文字列のビットマスク化）に文字数合計に比例する計算量、ペア比較にO(n²)の計算量が必要ですが、各比較自体は1回のビット演算で完結するため、素朴な文字照合よりもはるかに効率的です。文字種が英小文字26種類に限定されるため、32ビット整数1つで表現できる点もこの手法の大きな利点です。