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 uses memoization to improve performance. It's same as the recursive version of Longest palindromic subsequence (LPS), but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

def count(s, iKey, jKey):
  n = len(s)

  if n == 0:
    return 0

  if n == 1:
    return 1
  
  global cache
  if not cache:
    cache = [[None] * n for _ in range(n)]

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

s = 'character'

print(count(s, 0, len(s) -1))

// Javascript implementation

let cache = null;

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

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

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

  if (cache === null) {
    cache = Array(s.length);
    for (let i = 0; i < s.length; i++) {
      cache[i] = Array(s.length).fill(null);
    }
  }

  if (!cache[iKey][jKey]) {
    if (s.at(0) === s.at(-1)) {
      cache[iKey][jKey] = 2 + count(s.slice(1, -1), iKey + 1, jKey - 1);
    } else {
      cache[iKey][jKey] = Math.max(count(s.slice(1), iKey + 1, jKey), count(s.slice(0, -1), iKey, jKey - 1));
    }
  }

  return cache[iKey][jKey];
}

const str = 'character';

console.log(count(str, 0, str.length - 1));

Longest palindromic subsequence (LPS) (Memoization)

Hint