Input:  s = "bbbab"
Output: 4

Explanation: The longest palindromic subsequence is "bbbb" (length 4).
             Characters at positions 0,1,3,4: b, b, b, b.

Input:  s = "cbbd"
Output: 2

Explanation: The longest palindromic subsequence is "bb" (length 2).

String: "babad"

Longest Palindromic SUBSTRING:  "bab" or "aba" (CONTIGUOUS)
                                  positions 0-2 or 1-3

Longest Palindromic SUBSEQUENCE: "babab" or "badab" (NOT contiguous)
                                  positions 0,1,3,4,2 or 0,2,4,3,1

Subsequence can skip characters → more freedom → potentially longer result

dp[i][j] = length of longest palindromic subsequence in s[i..j] (inclusive)

If s[i] === s[j]:
    dp[i][j] = dp[i+1][j-1] + 2    // Match both ends → LPS extends by 2
Else:
    dp[i][j] = max(dp[i+1][j], dp[i][j-1])  // Skip one end, take best

dp[i][i] = 1                (single character is a palindrome of length 1)
dp[i][j] = 0 if i > j       (empty substring — no characters)

function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));

    // Base: single characters
    for (let i = 0; i < n; i++) dp[i][i] = 1;

    // Fill by length (increasing gap size)
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;

            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

console.log(longestPalindromeSubseq("bbbab")); // 4
console.log(longestPalindromeSubseq("cbbd"));  // 2

n=5, s = b b b a b

Step 1: Initialize diagonals (i=j → dp=1)
       0:b  1:b  2:b  3:a  4:b
0:b     1    ?    ?    ?    ?
1:b         1    ?    ?    ?
2:b             1    ?    ?
3:a                 1    ?
4:b                     1

Step 2: Fill len=2 (gap=1)
  dp[0][1]: b===b → dp[1][0]+2 = 0+2 = 2
  dp[1][2]: b===b → dp[2][1]+2 = 0+2 = 2
  dp[2][3]: b!==a → max(dp[3][3]=1, dp[2][2]=1) = 1
  dp[3][4]: a!==b → max(dp[4][4]=1, dp[3][3]=1) = 1

Step 3: Fill len=3 (gap=2)
  dp[0][2]: b===b → dp[1][1]+2 = 1+2 = 3
  dp[1][3]: b!==a → max(dp[2][3]=1, dp[1][2]=2) = 2
  dp[2][4]: b===b → dp[3][3]+2 = 1+2 = 3

Step 4: Fill len=4 (gap=3)
  dp[0][3]: b!==a → max(dp[1][3]=2, dp[0][2]=3) = 3
  dp[1][4]: b===b → dp[2][3]+2 = 1+2 = 3

Step 5: Fill len=5 (gap=4)
  dp[0][4]: b===b → dp[1][3]+2 = 2+2 = 4  ← ANSWER

Answer: dp[0][4] = 4 ("b-b-b-b" using characters 0,1,3,4)

function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = new Array(n).fill(1);  // Current row (diagonal)

    for (let len = 2; len <= n; len++) {
        let prev = 0;  // dp[i+1][j-1] for current j
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            const temp = dp[i];  // Save dp[i][j-1] before overwrite

            if (s[i] === s[j]) {
                // dp[i][j] = dp[i+1][j-1] + 2
                // dp[i] currently holds dp[i+1][j-1]... wait, let me rethink.
                // Actually, this optimization is complex. Let's keep the simpler version.
            }

            prev = temp;
        }
    }

    // For simplicity, stick with the 2D version or use reversed string trick
}

// Alternative O(n) space using LCS with reversed string:
function longestPalindromeSubseq(s) {
    const rev = s.split('').reverse().join('');
    return longestCommonSubsequence(s, rev);
}

function longestCommonSubsequence(a, b) {
    const n = b.length;
    let prev = new Array(n + 1).fill(0);

    for (let i = 1; i <= a.length; i++) {
        const curr = new Array(n + 1).fill(0);
        for (let j = 1; j <= n; j++) {
            if (a[i - 1] === b[j - 1]) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
        }
        prev = curr;
    }

    return prev[n];
}

console.log(longestPalindromeSubseq("bbbab")); // 4

s = "bbbab"
rev = "babbb"
LCS(s, rev) = "bbbb" (length 4) — which is the LPS! ✓

function minInsertions(s) {
    const n = s.length;
    const lps = longestPalindromeSubseq(s);
    return n - lps;  // Insert the missing characters to make the palindrome
}

console.log(minInsertions("mbadm")); // 2
// "mbadm" → "mbdadbm" (insert 'b' and 'd')
// LPS length = 3 ("mam" or "mdm")
// n - LPS = 5 - 3 = 2 insertions