3. Longest Palindromic Substring

LC5

Given a string s, return *the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Approach:

Using Expansion from center

Intuition:

The LPS is either of even length or odd length. So the idea is to traverse the input string and for each character check if this character can be the center of a palindromic substring of odd length or even length.

Follow the steps mentioned below to implement the idea:

• Use two pointers, low and high, for the left and right end of the current palindromic substring being found.
• Then checks if the characters at str[low] and str[high] are the same.
  • If they are, it expands the substring to the left and right by decrementing low and incrementing high.
  • It continues this process until the characters at str[low] and str[high] are unequal or until the indices are in bounds.
• If the length of the current palindromic substring becomes greater than the maximum length, it updates the maximum length.

Implementation 1:

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let n = s.length;
  if (n==0) {
      return -1;
  }
  let start = 0;
  let end = 0;
  let maxLen = 0;
  // odd
  for(let i=0; i<n; i++) {
      let left = i;
      let right = i;
      while(left >= 0 && right < n) {
          if (s[left] === s[right]) {
              left--;
              right++;
          } else {
              break;
          }
      }
      let len = right-left-1;
      if (len>maxLen) {
          maxLen = len;
          start = left+1;
          end = right-1;
      }
  }

  // even
  for(let i=0; i<n; i++) {
      let left = i;
      let right = i+1;
      while (left >=0 && right < n) {
          if (s[left] === s[right]) {
              left--;
              right++;
          } else {
              break;
          }
      }
      let len = right-left-1;
      if (len>maxLen) {
          maxLen = len;
          start = left+1;
          end = right-1;
      }
  }
  return s.substring(start, end+1);
} 

To make this better we can move common part to a new function getSubstringIndexes

Implementation 2:

const getSubstringIndexes = function (maxLen, left, right, s, n) {
  while (left >= 0 && right < n) {
    if (s[left] === s[right]) {
      left--;
      right++;
    } else {
      break;
    }
  }
  let len = right - left - 1;
  if (len > maxLen) {
    maxLen = len;
    start = left + 1;
    end = right - 1;
  }
  return {
    maxLen,
    start,
    end,
  };
};

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let n = s.length;
  if (n == 0) {
    return -1;
  }
  let start = 0;
  let end = 0;
  let maxLen = 0;
  // odd
  for (let i = 0; i < n; i++) {
    let left = i;
    let right = i;
    const {
      start: newStart,
      end: newEnd,
      maxLen: maxLength,
    } = getSubstringIndexes(maxLen, left, right, s, n);
    start = newStart;
    end = newEnd;
    maxLen = maxLength;
  }

  // even
  for (let i = 0; i < n; i++) {
    let left = i;
    let right = i + 1;
    const {
      start: newStart,
      end: newEnd,
      maxLen: maxLength,
    } = getSubstringIndexes(maxLen, left, right, s, n);
    start = newStart;
    end = newEnd;
    maxLen = maxLength;
  }
  return s.substring(start, end + 1);
};

Complexity Analysis:

Time complexity: O(n^2) Space complexity: O(1)