JavaScript: Longest Palindromic Subsequence

Last update on March 05 2025 10:40:58 (UTC/GMT +8 hours)

JavaScript String: Exercise-63 with Solution

Longest Palindromic Subsequence

Write a JavaScript function to find the length of the longest palindromic subsequence in a given string.
Subsequences are sequences that can be created by deleting some or all of the elements from another sequence without changing their order.
Test Data:
("aaaba") -> 4
("maadaem") -> 5
("zkksk") -> 3
("ab") -> 1
("") -> ""

Sample Solution:

JavaScript Code:

 // Define a function called 'test' with a parameter 'text'
const test = function(text) {
    // Check if the input 'text' is not a string, return a message
    if (typeof text !== 'string') {
        return 'It must be string'
    } 
    // Get the length of the input string 'text'
    const n = text.length
    // If the length of the string is 0, return the input string
    if (n==0) {
        return text
    }
    // Initialize a 2D array 'data' with dimensions 'n x n' filled with zeros
    const data = new Array(n).fill(0).map(item => new Array(n).fill(0).map(item => 0))
    // Set diagonal elements of 'data' to 1
    for (let i = 0; i < n; i++) {
        data[i][i] = 1
    }

    // Iterate through each character of the input string 'text'
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n - i; j++) {
            // Calculate the column index
            const col = j + i
            // If the characters at indices 'j' and 'col' are equal
            if (text[j] === text[col]) {
                // Update 'data' with the length of the palindrome by adding 2 to the value of the previous diagonal element
                data[j][col] = 2 + data[j + 1][col - 1]
            } else {
                // Otherwise, update 'data' with the maximum value from the adjacent elements
                data[j][col] = Math.max(data[j][col - 1], data[j + 1][col])
            }
        }
    }
    // Return the length of the longest palindromic subsequence, which is stored at data[0][n - 1]
    return data[0][n - 1]
}

// Test the 'test' function with different input strings and output the result
console.log(test("aaaba"))    // Output: 4
console.log(test("maadaem"))  // Output: 5
console.log(test("zkksk"))    // Output: 3
console.log(test("ab"))       // Output: 1
console.log(test(""))         // Output: ""

Output:

Explanation:

In the exercise above,

The function checks if the input 'text' is not a string, in which case it returns a message.
It gets the length of the input string 'text'.
If the length of the string is 0, it returns the input string itself.
It initializes a 2D array 'data' with dimensions 'n x n' filled with zeros, where 'n' is the length of the input string.
It sets the diagonal elements of 'data' to 1, representing single characters as palindromes.
It iterates through each character of the input string and calculates the length of the longest palindromic subsequence using dynamic programming.
It returns the length of the longest palindromic subsequence, which is stored at 'data[0][n - 1]'.

Flowchart:

Live Demo:

For more Practice: Solve these Related Problems:

Write a JavaScript function that finds the length of the longest palindromic subsequence in a string using recursion with memoization.
Write a JavaScript function that implements a dynamic programming solution to determine the longest palindromic subsequence.
Write a JavaScript function that returns both the length and the subsequence itself from the given string.
Write a JavaScript function that handles empty strings and returns a default value when no palindrome exists.

Improve this sample solution and post your code through Disqus.

Previous: Longest Valid Parentheses.
Next: JavaScript Bit Manipulation Exercises Home.