1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
 * Find the length of the longest palindromic subsequence in a string.
 * Dynamic Programming approach.
 * 
 * @param {string} s - The input string
 * @return {number} - The length of the longest palindromic subsequence
 */
function longestPalindromeSubseq(s) {
  const n = s.length;
  
  // Create a 2D DP table
  const dp = Array(n).fill().map(() => Array(n).fill(0));
  
  // Base case: single characters are palindromes of length 1
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }
  
  // Fill the DP table diagonally
  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];
}
 
/**
 * Find the length of the longest palindromic subsequence in a string.
 * Space-Optimized Dynamic Programming approach.
 * 
 * @param {string} s - The input string
 * @return {number} - The length of the longest palindromic subsequence
 */
function longestPalindromeSubseqOptimized(s) {
  const n = s.length;
  
  // Initialize previous array with 1s (base case)
  let previous = Array(n).fill(1);
  
  // Fill the arrays diagonally
  for (let len = 2; len <= n; len++) {
    const current = Array(n).fill(0);
    
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      
      if (s[i] === s[j]) {
        current[i] = (i + 1 <= j - 1 ? previous[i + 1] : 0) + 2;
      } else {
        current[i] = Math.max(
          (i + 1 < n ? current[i + 1] : 0),
          previous[i]
        );
      }
    }
    
    previous = current;
  }
  
  return previous[0];
}
 
/**
 * Find the length of the longest palindromic subsequence in a string.
 * Recursive approach with memoization.
 * 
 * @param {string} s - The input string
 * @return {number} - The length of the longest palindromic subsequence
 */
function longestPalindromeSubseqRecursive(s) {
  const n = s.length;
  
  // Create a memoization table
  const memo = Array(n).fill().map(() => Array(n).fill(-1));
  
  // Recursive function with memoization
  function lps(i, j) {
    // Base cases
    if (i > j) return 0;
    if (i === j) return 1;
    
    // Check if we've already computed this subproblem
    if (memo[i][j] !== -1) return memo[i][j];
    
    // Recursive cases
    if (s[i] === s[j]) {
      memo[i][j] = lps(i + 1, j - 1) + 2;
    } else {
      memo[i][j] = Math.max(lps(i + 1, j), lps(i, j - 1));
    }
    
    return memo[i][j];
  }
  
  return lps(0, n - 1);
}
 
// Test cases
console.log(longestPalindromeSubseq("bbbab"));  // 4
console.log(longestPalindromeSubseq("cbbd"));   // 2
console.log(longestPalindromeSubseq("linguistics"));  // 3
 
console.log(longestPalindromeSubseqOptimized("bbbab"));  // 4
console.log(longestPalindromeSubseqOptimized("cbbd"));   // 2
console.log(longestPalindromeSubseqOptimized("linguistics"));  // 3
 
console.log(longestPalindromeSubseqRecursive("bbbab"));  // 4
console.log(longestPalindromeSubseqRecursive("cbbd"));   // 2
console.log(longestPalindromeSubseqRecursive("linguistics"));  // 3