【JavaScript】2つの配列間の文字列の長さにおける最大絶対差を求める方法

問題

2つの文字列の配列 a1 と a2 を引数として受け取るJavaScript関数を作成する必要があります。各文字列は a〜z の英字のみで構成されているものとします。ここで x を1つ目の配列内の任意の文字列、y を2つ目の配列内の任意の文字列としたとき、関数は次の値を求めます。

max(abs(length(x) − length(y)))

つまり、別々の配列に属する文字列のペアごとに長さの差の絶対値を計算し、その中で最大となる値を返すという問題です。

解法のポイント

すべての文字列の組み合わせに対して二重ループで差を求めることも可能ですが、より効率的なアプローチがあります。絶対差が最大になるのは、必ず「片方の配列の最長文字列」と「もう片方の配列の最短文字列」の組み合わせであるため、各配列の文字列長の最大値と最小値さえ分かれば計算できます。

具体的には、Math.max(配列1の最大長 − 配列2の最小長, 配列2の最大長 − 配列1の最小長) を返すだけでよく、O(n) の計算量で結果を導き出せます。また、どちらかの配列が空の場合は比較が不可能なため、-1 を返す仕様とします。

コード例

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

const arr1 = ["hoqq", "bbllkw", "oox", "ejjuyyy", "plmiis", "xxxzgpsssa", "xxwwkktt", "znnnnfqknaz", "qqquuhii", "dvvvwz"];
const arr2 = ["cccooommaaqqoxii", "gggqaffhhh", "tttoowwwmmww"];
const findMaxAbsDiff = (arr1 = [], arr2 = []) => {
    if(arr1.length === 0 || arr2.length === 0){
        return -1;
    };
    let l1 = arr1.map(str => str.length)
    let l2 = arr2.map(str => str.length)
    return Math
    .max(Math.max(...l1) - Math.min(...l2), Math.max(...l2) - Math.min(...l1));
};
console.log(findMaxAbsDiff(arr1, arr2));

出力

13

処理の流れの解説

• まず、どちらかの配列が空であれば -1 を返して処理を終了します。
• map() を使って、各配列の文字列を文字数（数値）の配列へ変換します。
• スプレッド構文 ... で Math.max と Math.min に値を渡し、両方向の差を比較します。これにより abs() を明示的に呼び出さなくても最大絶対差が求まります。
• この例では、arr2 の最長文字列「cccooommaaqqoxii」（16文字）と arr1 の最短文字列「oox」（3文字）の差が 13 となり、これが最大値となります。