String Dynamic Programming Tabulation
Proficient Level

Implement the longestPalindromicSubsequenceLength method that returns the length of the longest palindromic subsequence.

The input contains a string text. Your task is to return the length of the longest palindromic subsequence in that string.

A subsequence keeps the original character order but does not need to use continuous characters. A palindrome reads the same from both sides. For example, in bbbab, the subsequence bbbb is palindromic, so the answer is 4.

Example 1
Input:
text (string) = bbbab
Return:
(int) 4
Example 2
Input:
text (string) = cbbd
Return:
(int) 2
Example 3
Input:
text (string) = a
Return:
(int) 1

Use dynamic programming on ranges of the string.

Let dp[left][right] store the longest palindromic subsequence length inside the substring from left to right.

If the two end characters match, they can be part of the same palindrome, so add 2 to the answer inside the range. If they do not match, remove one end at a time and keep the larger result.

Pseudocode:

function longestPalindromicSubsequenceLength(text):
    n = length(text)
    dp = 2D array of size n x n filled with 0
    for i from 0 to n - 1:
        dp[i][i] = 1
    for lengthValue from 2 to n:
        for left from 0 to n - lengthValue:
            right = left + lengthValue - 1
            if text[left] == text[right]:
                dp[left][right] = 2 + dp[left + 1][right - 1]
            else:
                dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
    return dp[0][n - 1]
Run your code to see the result.