Longest Palindromic Substring

Given a string S, we need to find length of its Longest Palindromic Substring. Palindrome is a string that reads the same backwards as well as forward and can be odd or even length. A substring is a contiguous sequence of characters within a string.

Example 1
-----------
s: "ABCYRCFBTUA"
output: 1
Explanation: "ABCYRCFBTUA" => "A"
              ^

Example 2
-----------
s: "ABCCBUA"
output: 4
Explanation: "ABCCBUA" => "BCCB"
               ^^^^

Example 3
-----------
s: "MQADASM"
output: 3
Explanation: "MQADASM" => "ADA"
                ^^^

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(2,6) only if the remaining characters are palindrome ---|--- max
If it doesn't match: max of [0 + f(2,7)] or [0 + f(1,6)]                                            ---|

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(2,6). However, if the remaining characters are not palindrome, we should not increase our answer by 2 since we are looking for substring which needs to be contiguous. 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(2,7)] or [0 + f(1,6)].

Code Algortihm

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

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

  const count2 = lps(str, start, end - 1);
  const count3 = lps(str, 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,8)
    /               |               \
  lps(1,7)        lps(1,8)        lps(0,7)
  |                |                |
  |-lps(2,6)       |-lps(2,7)       |-lps(1,6)
  |-lps(2,7)       |-lps(2,8)       |-lps(1,7)
  |-lps(1,6)       |-lps(1,7)       |-lps(0,6)

We are computing a new of the subproblems more than once such as lps(1,7). 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(str: string, start: number, end: number): number {
  if (start > end) return 0;
  if (start === end) return 1;

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

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

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

    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.

To achieve bottom up approach, we then need to solve row by row starting from the last row.

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

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

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

      if (row > col) {
        dp[row][col] = 0;
      } else if (row === col) {
        dp[row][col] = 1;
      } else {
        if (str[row] === str[col]) {
          length = 0;
          remainingLen = col - row - 1;
          if (remainingLen  === dp[row + 1][col - 1]) {
            length = 2;
          }
          dp[row][col] = Math.max(length + 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][str.length - 1];
}