JavaScriptで文字列配列の最長の非共通部分列（Longest Uncommon Subsequence）を求める方法

部分列（Subsequence）とは

まず用語を整理しましょう。「部分列」とは、元の文字列から一部の文字を削除して得られる列であり、残りの文字の相対的な順序は変更しないものを指します。たとえば「ace」は「abcde」の部分列ですが、「aec」は順序が異なるため部分列ではありません。

なお、任意の文字列はそれ自身の部分列として扱われ、空文字列はあらゆる文字列の部分列であると定義します。

問題の定義

今回求めるのは、次のようなJavaScript関数です。

• 引数として文字列の配列を1つ受け取る
• 配列内のいずれかの文字列の部分列でありながら、他のどの文字列の部分列でもないような「非共通部分列」のうち、最も長いものの長さを返す
• 非共通な部分列がひとつも存在しない場合は -1 を返す

入力例

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

期待される出力

const output = 3;

出力の解説：「aba」「cdc」「eae」は互いに他方の部分列ではないため、それぞれ長さ3の有効な非共通部分列となります。したがって答えは3です。

アプローチ

この問題を確実に解くためのシンプルな戦略は次のとおりです。

1. 各文字列について、それが他のすべての文字列の部分列になっているかを順番にチェックします。
2. ひとつでも部分列になってしまう相手があれば、その文字列は候補から除外します。
3. 除外されなかった文字列（＝非共通な部分列となり得る文字列）の中で最大の長さを答えとします。該当がなければ -1 を返します。

2つの文字列 a と b に対して「a が b の部分列か」を判定するには、b を先頭から走査し、a の文字と一致するごとにポインタを進めていく方法が使えます。走査終了時にポインタが a の長さに達していれば、a は b の部分列です。

コード例

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

const longestUncommon = (strs) => {
   // a が b の部分列かどうかを判定するヘルパー関数
   const isSubsequence = (a, b) => {
      let i = 0;
      for (const ch of b) {
         if (ch === a[i]) i++;
      }
      return i === a.length;
   };

   let max = -1;
   for (let i = 0; i < strs.length; i++) {
      // 他のどの文字列の部分列でもなければ「非共通」
      const isUncommon = strs.every(
         (other, j) => j === i || !isSubsequence(strs[i], other)
      );
      if (isUncommon && strs[i].length > max) {
         max = strs[i].length;
      }
   }
   return max;
};

console.log(longestUncommon(arr));

出力

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

3

計算量について

文字列の数を n、各文字列の平均的な長さを m とすると、すべてのペアに対して部分列判定を行うため、時間計算量は O(n² × m) になります。部分列判定自体は線形時間で完了するため、入力サイズが現実的な範囲であれば十分高速に動作します。

補足：重複した文字列の扱い

同じ文字列が配列内に2回以上登場する場合、その文字列は互いの部分列となるため自動的に候補から除外されます。また、ある文字列が別のより長い文字列に含まれる形で出現する場合も同様に除外されます。このロジックにより、非共通部分列が存在しないケース（すべての文字列が相互に部分列関係にあるケース）では正しく -1 が返されます。