JavaScriptで最も長い非共通部分列（LUS）を見つける方法

文字列の配列を受け取り、その中から最長非共通部分列（Longest Uncommon Subsequence）を見つけるJavaScript関数を作成する必要があります。

ここで「最長非共通部分列」とは、配列内のいずれか1つの文字列の部分列でありながら、他のどの文字列の部分列としても現れない、最長の部分列のことを指します。

この関数は、そのような最長非共通部分列の長さを返す必要があります。

問題の例

例えば、入力配列が次のようになっているとします。

const arr = ["aba", "cdc", "eae"];

この場合、出力は 3 になります。「aba」「cdc」「eae」は互いに他方の部分列ではないため、最も長い非共通部分列の長さは、これらの文字列のうち最も長いものの長さである3となるからです。

解き方のポイント

この問題を解く際の基本的な考え方は以下の通りです。

• 各文字列が配列内に出現する回数を記録します。
• すべての文字列が互いに異なり、どの文字列も他の文字列の部分列になっていない場合、答えは単純に最も長い文字列の長さになります。
• 一方、ある文字列が別の文字列の部分列として含まれる場合は、その文字列は「非共通」ではないため候補から除外し、残った文字列の中で最も長いものの長さを求めます。

コード例

この問題に対する実装コードは次のようになります。

const arr = ["aba", "cdc", "eae"];
const findUncommonLength = (array = []) => {
    const seen = {};
    const arr = [];
    let max = -1;
    let index = -1;
    for(let i = 0; i < array.length; i++){
        seen[array[i]] = (seen[array[i]] || 0) + 1;
        if(seen[array[i]] > 1){
            if(max < array[i].length){
                max = array[i].length;
                index = i;
            }
        }
    };
    if(index === -1) {
        array.forEach(el => {
            if(el.length > max) max = el.length;
        });
        return max;
    };
    for(let i = 0; i < array.length; i++){
        if(seen[array[i]] === 1) arr.push(array[i]);
    };
    max = -1;
    for(let i = arr.length - 1; i >= 0; i--){
        let l = arr[i];
        let d = 0;
        for(let j = 0; j < array[index].length; j++){
            if(array[index][j] === l[d]){
                d++;
            }
        }
        if(d === l.length){
            let temp = arr[i];
            arr[i] = arr[arr.length - 1];
            arr[arr.length - 1] = temp;
            arr.pop();
        }
    };
    arr.forEach(el => {
        if(el.length > max) max = el.length;
    });
    return max;
};
console.log(findUncommonLength(arr));

コードの解説

まず、オブジェクト seen を使って各文字列の出現回数を数えています。重複する文字列が存在しない場合（index === -1 の場合）は、配列内で最も長い文字列の長さをそのまま返します。

重複が存在する場合は、一度だけ出現している文字列だけを新しい配列 arr に集めます。その後、各文字列が基準となる文字列の部分列になっているかを2ポインタ的な走査で判定し、部分列になっている要素を配列から取り除きます。最後に残った文字列の中で最大の長さを返すことで、最長非共通部分列の長さが得られます。

出力結果

上記のコードを実行すると、コンソールには次のように表示されます。

3