Longest palindromic subsequence (LPS)

Given a string, find the length of the longest palindromic subsequence in it. For example, the length of the longest palindromic subsequence for 'bbbab' is 4 and the sequence is 'bbbb'.

Hint

This algorithm counts the number of palindromic subsequences within a given string.

• If the first and last characters of the string are the same: The total count of palindromic subsequences is calculated by adding 2 to the count of palindromic subsequences within the substring that excludes the first and last characters.
• If the first and last characters of the string are different: Finding the maximum count between count of palindromic subsequences within the substring that excludes the first character, and count of palindromic subsequences within the substring that excludes the last character.

If the string is empty, it has zero palindromic subsequences (return 0). If the string contains only one character, it has one palindromic subsequence (the character itself) (return 1).

• Python
• Javascript
•  Run

def count(s):
  n = len(s)

  if n == 0:
    return 0

  if n == 1:
    return 1

  if s[0] == s[-1]:
    return 2 + count(s[1:-1])
  else:
    return max(count(s[1:]), count(s[0:-1]))

s = 'character'

print(count(s))

function count(s) {
  const n = s.length;

  if (n === 0) {
    return 0;
  }

  if (n === 1) {
    return 1;
  }

  if (s.at(0) === s.at(-1)) {
    return 2 + count(s.slice(1, -1));
  } else {
    return Math.max(count(s.slice(1)), count(s.slice(0, -1)));
  }
}

const str = 'character';

console.log(count(str));