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) =
bbbabReturns (int)
4Example 2
Input
text (string) =
cbbdReturns (int)
2Example 3
Input
text (string) =
aReturns (int)
1Use 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run