JavaScript: Longest Palindromic Subsequence

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:

4
5
3
1

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:

See the Pen javascript-string-exercise-63 by w3resource (@w3resource) on CodePen.

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.

Go to:

• JavaScript String Exercises Home ↩
• JavaScript Exercises Home ↩

PREV : Longest Valid Parentheses.
NEXT : JavaScript Bit Manipulation Exercises Home.

Improve this sample solution and post your code through Disqus.