最長共通部分列（LCS）の求め方について、図を使って具体的に説明します。
例として、入力 "mynavi" と "monday" を考えます。

S = "mynavi" (長さ6)
T = "monday" (長さ6)
まず、長さ (S.length + 1) × (T.length + 1) の 2D 配列 dp を作ります（初期値はすべて0）。
dp[i][j] は S[0..i-1] と T[0..j-1] の最長共通部分列の長さを表します。

    0  m  o  n  d  a  y
  ----------------------
0 | 0  0  0  0  0  0  0
m | 0
y | 0
n | 0
a | 0
v | 0
i | 0

S[i-1] === T[j-1] の場合 dp[i][j] = dp[i-1][j-1] + 1
一致しない場合 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

1. 1行目（m）の更新
   • S[0] = "m" と T[0] = "m" が一致 → dp[1][1] = 1
   • それ以外の列は dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    0  m  o  n  d  a  y
  ----------------------
0 | 0  0  0  0  0  0  0
m | 0  1  1  1  1  1  1
y | 0
n | 0
a | 0
v | 0
i | 0

2. 2行目（y）の更新
   • S[1] = "y" と T[5] = "y" が一致 → dp[2][6] = 2
   • それ以外は dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    0  m  o  n  d  a  y
  ----------------------
0 | 0  0  0  0  0  0  0
m | 0  1  1  1  1  1  1
y | 0  1  1  1  1  1  2
n | 0
a | 0
v | 0
i | 0

3. 3行目（n）の更新
   • S[2] = "n" と T[2] = "n" が一致 → dp[3][3] = 2
   • dp[i][j] = max(dp[i-1][j], dp[i][j-1]) を適用

    0  m  o  n  d  a  y
  ----------------------
0 | 0  0  0  0  0  0  0
m | 0  1  1  1  1  1  1
y | 0  1  1  1  1  1  2
n | 0  1  1  2  2  2  2
a | 0
v | 0
i | 0

4. 4行目（a）の更新
   • S[3] = "a" と T[4] = "a" が一致 → dp[4][5] = 3

    0  m  o  n  d  a  y
  ----------------------
0 | 0  0  0  0  0  0  0
m | 0  1  1  1  1  1  1
y | 0  1  1  1  1  1  2
n | 0  1  1  2  2  2  2
a | 0  1  1  2  2  3  3
v | 0
i | 0

5. 5行目（v）の更新
   • 一致する文字がないため dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    0  m  o  n  d  a  y
  ----------------------
0 | 0  0  0  0  0  0  0
m | 0  1  1  1  1  1  1
y | 0  1  1  1  1  1  2
n | 0  1  1  2  2  2  2
a | 0  1  1  2  2  3  3
v | 0  1  1  2  2  3  3
i | 0

6. 6行目（i）の更新
   • 一致する文字がないため dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    0  m  o  n  d  a  y
  ----------------------
0 | 0  0  0  0  0  0  0
m | 0  1  1  1  1  1  1
y | 0  1  1  1  1  1  2
n | 0  1  1  2  2  2  2
a | 0  1  1  2  2  3  3
v | 0  1  1  2  2  3  3
i | 0  1  1  2  2  3  3

最後のセル dp[S.length][T.length] の値が LCS の長さ。
この場合 dp[6][6] = 3 なので、最長共通部分列の長さは 3 です。

• DP テーブルを作り、S, T の各文字を比較しながら更新する
• 最長共通部分列の長さは dp[S.length][T.length] に格納される
• 計算量は O(m×n) であり、最大 2000×2000 でも問題なく動作

現在の実装は O(m×n) の時間計算量 と O(m×n) のメモリ使用量 ですが、メモリを削減し、さらに高速化する方法があります。

現在の dp テーブルは O(m×n) の 2D 配列ですが、実は O(n) の 1D 配列 に圧縮できます。

• dp[i][j] の更新では、dp[i-1][*] のみを使うため、2 行（prev と curr）があれば十分
• prev[j] で前の行の情報を保持し、curr[j] で現在の計算をする
• 計算後 prev = curr に更新して次の行へ

function longestCommonSubsequence(S, T) {
    const m = S.length,
        n = T.length;
    let prev = new Array(n + 1).fill(0);
    let curr = new Array(n + 1).fill(0);

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (S[i - 1] === T[j - 1]) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
        }
        [prev, curr] = [curr, prev]; // メモリを節約するため swap
    }

    return prev[n];
}

• O(m×n) → O(n) に削減
• prev と curr の 2 行分のみ保存 すれば十分（合計 O(2n) ≈ O(n)）

DP の計算量 O(m×n) は本質的に最適だが、さらなる高速化の方法もある。

最長増加部分列（LIS）と同様に 座標圧縮 + Fenwick Tree / Segment Tree を使うと O(n log n) に改善できる。

• 手順
  1. S の各文字の出現位置リストを作成
  2. T を走査しながら、S に対応する文字の位置リストを二分探索して最長増加部分列（LIS）を求める

これは難易度が高いが、2000×2000 のサイズがギリギリの場合、実行時間短縮に有効。

DP の計算回数を減らすため、一般的な最適化技法を試す：

1. S.length < T.length のとき入れ替え
   • S の方が短い方がメモリ削減の恩恵を受けやすい
2. T をハッシュセット化
   • 文字の出現有無を Set で管理し、S の不要な計算をスキップ
3. Early stopping
   • 例えば dp[i][n] == dp[m][n] なら、i より後ろを計算する必要なし

通常の DP 配列 dp[i][j] を更新するとき、前の行（dp[i-1][*]）しか参照しない ため、2行分のデータだけを保存すれば十分 です。

具体的には：

• prev 配列 を dp[i-1][*] として使う（前の行）
• curr 配列 を dp[i][*] として使う（現在の行）
• 計算が終わったら prev = curr にして、次の行に進む

これにより、メモリ使用量を O(m×n) → O(n) に削減 できます。

mynavi の長さ = 6, monday の長さ = 6 の場合、
通常の dp テーブルは 7×7 の 2D 配列ですが、2 行の 1D 配列 prev と curr に圧縮できます。

配列 prev と curr を長さ n+1（=7）の配列として 0 で初期化：

prev: [0, 0, 0, 0, 0, 0, 0]
curr: [0, 0, 0, 0, 0, 0, 0]

m == m なので curr[1] = prev[0] + 1 = 1
curr[j] = max(prev[j], curr[j-1]) を適用

→ prev を curr に更新

prev: [0, 1, 1, 1, 1, 1, 1]
curr: [0, 0, 0, 0, 0, 0, 0]  (リセット)

y == y なので curr[6] = prev[5] + 1 = 2
他の curr[j] は max(prev[j], curr[j-1])

→ prev を curr に更新

prev: [0, 1, 1, 1, 1, 1, 2]
curr: [0, 0, 0, 0, 0, 0, 0]  (リセット)

n == n なので curr[3] = prev[2] + 1 = 2
他の curr[j] は max(prev[j], curr[j-1])

→ prev を curr に更新

prev: [0, 1, 1, 2, 2, 2, 2]
curr: [0, 0, 0, 0, 0, 0, 0]  (リセット)

a == a なので curr[5] = prev[4] + 1 = 3
他の curr[j] は max(prev[j], curr[j-1])

→ prev を curr に更新

prev: [0, 1, 1, 2, 2, 3, 3]
curr: [0, 0, 0, 0, 0, 0, 0]  (リセット)

一致する文字がないため、すべて max(prev[j], curr[j-1])

最終結果

prev: [0, 1, 1, 2, 2, 3, 3]

LCS の長さは prev[6] = 3

1. prev 配列だけを保持し、curr を使って更新
2. 計算が終わったら prev = curr にして前行を置き換える
3. 最終的に prev[n] に LCS の長さが格納される

この方法で O(m×n) の計算時間はそのままに、メモリを O(n) に削減 できます！

ヒューリスティックな最適化では、以下の3つの手法を組み合わせて計算量を削減します。
この最適化により、余計な計算を省略し、高速に LCS（最長共通部分列）の長さを求めることができます。

LCS の計算は O(m × n) なので、m が小さい方がメモリ効率が良くなります。
もし S.length > T.length なら、S と T を入れ替えることで 行数（メモリ使用量）を減らせる ため、計算が速くなります。

if (S.length > T.length) {
    [S, T] = [T, S]; // S の方が短くなるようにする
}

S の各文字が T に存在しない場合、その文字を使う LCS の計算をする必要がありません。
このため、T の文字をハッシュセットに保存し、S の文字をフィルタリング できます。

1. T の文字を Set に格納
2. S の文字をフィルタリングし、T に存在するものだけを残す
3. DP の計算量が減る

const tSet = new Set(T); // T の文字を保存
S = S.split('')
    .filter((c) => tSet.has(c))
    .join(''); // S の不要な文字を削除

dp[i][n] の値が最終結果と同じなら、これ以上の計算は不要になります。
例えば、もし dp[i][n] == dp[m][n] なら、それ以上の i の計算を省略できます。

1. 各 i について prev[n] の値を監視
2. prev[n] が最終的な dp[m][n] と等しくなったら ループを打ち切る

for (let i = 1; i <= m; i++) {
    let stopEarly = true;
    for (let j = 1; j <= n; j++) {
        if (S[i - 1] === T[j - 1]) {
            curr[j] = prev[j - 1] + 1;
        } else {
            curr[j] = Math.max(prev[j], curr[j - 1]);
        }
        if (curr[j] !== curr[j - 1]) stopEarly = false; // 変化があれば続行
    }
    if (stopEarly) break; // 変化がないならループを終了
    [prev, curr] = [curr, prev]; // 配列をスワップ
}

• S.length = 6, T.length = 6 なので変更なし

• T = "monday" の文字を Set に格納

  tSet = { 'm', 'o', 'n', 'd', 'a', 'y' }
  

• S = "mynavi" のうち T にない v を削除

  S = "mynai"
  

• S の長さが 6 → 5 に短縮され、計算量が削減

最終的な LCS の長さは 3 です。

function longestCommonSubsequence(S, T) {
    if (S.length > T.length) [S, T] = [T, S]; // S の方が短くなるように

    const tSet = new Set(T);
    S = S.split('')
        .filter((c) => tSet.has(c))
        .join(''); // S の不要な文字を削除

    const m = S.length,
        n = T.length;
    let prev = new Array(n + 1).fill(0);
    let curr = new Array(n + 1).fill(0);

    for (let i = 1; i <= m; i++) {
        let stopEarly = true;
        for (let j = 1; j <= n; j++) {
            if (S[i - 1] === T[j - 1]) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
            if (curr[j] !== curr[j - 1]) stopEarly = false;
        }
        if (stopEarly) break;
        [prev, curr] = [curr, prev];
    }

    return prev[n];
}

// テスト
console.log(longestCommonSubsequence('mynavi', 'monday')); // 3
console.log(longestCommonSubsequence('tokyo', 'kyoto')); // 3

この最適化を適用すると：

1. 計算する S の長さを短縮（最大 50% 削減）
2. 無駄なループを省略（Early Stopping）
3. 計算量が O(m×n) から O(m'×n) に削減（m' は削減後の S の長さ）

この方法により、最悪ケースでも 高速に LCS を求めることが可能 になります！ 🚀