5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

Python

Forces Bust (Timeout)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        longest = ""
        for left in range(len(s)):
            for right in range(left, len(s)):
                candidate = s[left:right+1]
                if candidate == candidate[::-1]:
                    longest = candidate if len(candidate) > len(longest) else longest
        return longest

Expand from center

class Solution:
    def longestPalindrome(self, s: str) -> str:
        segment = s[0]

        for cur in range(len(s)):
            # Consider cur as middle (length are odd)
            for step in range(1, len(s)//2+1):
                if cur - step < 0 or cur + step > len(s)-1:
                    break
                if s[cur-step] == s[cur+step]:
                    if step*2+1 > len(segment):
                        segment = s[cur-step:cur+step+1]
                else:
                    break

            # Consider center is between cur & cur+1 (length are even)
            if cur + 1 >= len(s):
                continue

            left, right = cur, cur+1
            if s[left] != s[right]:
                continue

            while left-1 >= 0 and right+1 < len(s):
                if s[left-1] == s[right+1]:
                    left -= 1
                    right += 1
                else:
                    break

            if right - left + 1 > len(segment):
                segment = s[left:right+1]

        return segment

Javascript

var longestPalindrome = function(s) {
  const dp = [...new Array(s.length)].map(() => new Array(s.length).fill(false));

  let ans = ''
  for (let i = 0; i < s.length; i++) {
    dp[i][i] = true;
    ans = s[i];
  }

  let maxLen = 1;
  for (let start = s.length - 2; start >= 0; start--) {
    for (let end = start + 1; end < s.length; end++) {
      if (s[start] === s[end]) {
        if (start + 1 === end || dp[start + 1][end - 1]) {
          dp[start][end] = true;
          const tmpLen = end - start + 1;
          if (maxLen < tmpLen) {
            maxLen = end - start + 1;
            ans = s.slice(start, end + 1)
          }
        }
      }
    }
  }
  
  return ans;
};