One Pager Cheat Sheet

• Find the length of the longest palindromic subsequence of a given string s, consisting of only lowercase English letters and with length no greater than 1000.
• A brute-force approach to checking for the longest palindromic subsequence could be to directly check for palindromic subsequences and find the one with the longest length.
• The brute force approach to finding the length of the longest palindromic subsequence involves checking all possible subsequences of the given string, and is not ideal due to its exponential time complexity.
• We can reduce the time complexity of our problem by utilizing the bottom-up dynamic programming approach, which uses a 2D grid to store the result of each subproblem and reference it in constant time.
• Dynamic programming is a technique used to solve problems through breaking them down into smaller subproblems that exhibit optimal substructure and overlapping subproblems, allowing us to solve them using a bottom-up tabulation approach to store the results of each subproblem.
• We fill a 4 x 4 grid by traversing the given string s "cbbd" with two pointers, one working in reverse and the other traversing normally, to store the length of the longest palindromic subsequence encountered so far.
• Fill the grid[i][j] with 1 for diagonals that represent one element, as the length of the palindromic subsequence for one character is 1.
• All elements below the diagonal of the table should be set to 0 as they represent invalid subsequences due to their start point being after their end point.
• We traverse the grid bottom-up to find the length of the Longest Palindromic Subsequence which is returned by the top-right element of the matrix.
• The time complexity of the solution is O(n<sup>2</sup>), as it takes n2 time to create, traverse and fill the 2D grid of size n x n.
• The problem can be solved using the memoization approach of dynamic programming, reducing the time complexity to O(n<sup>2</sup>).

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function longestPalindromeSubseq(s) {

    if (!s) {

        return 0;

    }

    let grid = Array(s.length).fill('').map(() => Array(s.length).fill(0));

    for (let i = s.length - 1; i >= 0; i--) {

        grid[i][i] = 1;

        for (let j = i + 1; j < s.length; j++) {

            if (s[i] == s[j]) {

                grid[i][j] = grid[i + 1][j - 1] + 2;

            } else {

                grid[i][j] = Math.max(grid[i + 1][j], grid[i][j - 1]);

            }

        }

    }

    return grid[0][s.length - 1];

}

​

try {

    assert.deepEqual(longestPalindromeSubseq('bbbab'), 4);

    console.log('PASSED: ' + "`longestPalindromeSubseq('bbbab')` should return `4`");

} catch (err) {

    console.log(err);

}

​

try {

    assert.deepEqual(longestPalindromeSubseq('cbbd'), 2);

    console.log('PASSED: ' + "`longestPalindromeSubseq('cbbd')` should return `2`");

} catch (err) {

    console.log(err);

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.