Longest Palindromic Subsequence

Given a string S, we need to find the length of its Longest Palindromic Subsequence. Palindrome is a string that reads the same backwards as well as forward and can be odd or even length. A subsequence is a sequence that can be derived from another string by deleting some or no elements without changing the order of the remaining elements.

Example 1
-----------
s: "ELRMENMET"
output: 5
Explanation: "ELRMENMET" => "EMEME"
              ^  ^^ ^^

Example 2
-----------
s: "AMEEWMEA"
output: 6
Explanation: "AMEEWMEA" => "AMEEMA"
              ^^^^ ^ ^

Solution

This problem can be solved by applying Divide and Conquer to break down the problem into smaller subproblems. Thus, by solving these subproblems, we will arrive at our final answer. Let’s try to derive the subproblems.

If the first and last character matches: 2 + f(1,8)      ---|---max
If it doesn't match: max of [0 + f(0,8)] or [0 + f(1,9)] ---|

For palindrome, the first and last character should be the same so that it reads the same from the front and the back. Hence, to achive optimal substructure, if the first and last character matches, our answer increases by 2 and we move on to the next characters, hence, 2 + f(1,8). If it doesn’t match, we should then attempt to see if the next characters on both side matches and get the max value from it. Therefore, max of [0 + f(0,8)] or [0 + f(1,9)].

Code Algortihm

function lps(s: string, start: number, end: number): number {
  if (start > end) return 0;

  if (start === end) return 0;

  let count1 = 0;
  if (s[start] === s[end]) {
    count1 = 2 + lps(s, start + 1, end + 1);
  }

  count2 = lps(s, start, end - 1);
  count3 = lps(s, start + 1, end);

  return Math.max(count1, count2, count3);
}

Optimisation

Let’s look at the an example of the recursion tree see if we need to optimise this solution.

                lps(0,3)
    /               |               \
  lps(0,2)        lps(1,3)        lps(1,2)
  |                |                |
  |-lps(1,2)       |-lps(2,3)       |-lps(2,2)
  |-lps(0,1)       |-lps(1,2)       |-lps(1,1)
  |-lps(1,1)       |-lps(2,2)       |-lps(2,1)

We are computing a new of the subproblems more than once such as lps(1,2). We can then apply Dynamic Programming to optimise the solution.

Top Down Approach

We will start off by applying Top Down Approach (also known as Memoization).

type HashTable = {
  [x: number]: {
    [y: number]: number;
  };
};

const dp: HashTable = {};

function lps(s: string, start: number, end: number): number {
  if (start > end) return 0;

  if (start === end) return 0;

  if (!(start in dp) && !(end in dp[start])) {
    let count1 = 0;
    if (s[start] === s[end]) {
      count1 = 2 + lps(s, start + 1, end + 1);
    }

    count2 = lps(s, start, end - 1);
    count3 = lps(s, start + 1, end);

    if (!dp[start]) {
      dp[start] = {};
    }

    dp[start][end] = Math.max(count1, count2, count3);
  }

  return dp[start][end];
}

Bottom Up Approach

We can now then apply some reverse engineer to use the Bottom Up Approach (also known as Tabulation). Firstly, let’s start from looking at the Top Down Approach using a matrix table.

We then need to find the cell which doesn’t have any dependency as our starting point as we will have our first answer there. That would be the last cell A9B9. And we slowly move our way up to the rest of the cells until we reach cell A1B9 which will give us our final answer.

B8, A6 rows and columns are our base conditions where we return 0.

type HashTable = {
  [x: number]: {
    [y: number]: number;
  };
};


function lps(s: string): number {
  const dp: HashTable = {};

  for (let col = 0; col < s.length; ++col) {
    for (let row = s.length - 1; row > -1; --row) {
      if (!dp[row]) {
        dp[row] = {};
      }

      if (row > col) {
        dp[row][col] = 0;
      } else if (row === col) {
        dp[row][col] = 1;
      } else {
        if (s[row] === s[col]) {
          dp[row][col] = Math.max(2 + dp[row + 1][col - 1], dp[row][col - 1], dp[row + 1, col]);
        } else {
          dp[row][col] = Math.max(dp[row][col - 1], dp[row + 1][col]);
        }
      }
    }
  }

  return dp[0][s.length - 1];
}