longest-palindromic-substr

Longest Palindromic Substrings

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

Approach 1: Brute Force

def check(i, j):
    left = i
    right = j - 1
 
    while left < right:
        if s[left] != s[right]:
            return False
 
        left += 1
        right -= 1
 
    return True
 
for length in range(len(s), 0, -1):
    for start in range(len(s) - length + 1):
        if check(start, start + length):
            return s[start : start + length]
 
return ""

• Complexity: $O(n^3)$

Approach 2: DP

n = len(s)
dp = [[False] * n for _ in range(n)]
ans = [0, 0]
 
for i in range(n):
    dp[i][i] = True
 
for i in range(n - 1):
    if s[i] == s[i + 1]:
        dp[i][i + 1] = True
        ans = [i, i + 1]
 
for diff in range(2, n):
    for i in range(n - diff):
        j = i + diff
        if s[i] == s[j] and dp[i + 1][j - 1]:
            dp[i][j] = True
            ans = [i, j]
 
i, j = ans
return s[i : j + 1]

• Intuition
  • Check palindrome from center to edges
  • All characters are palindromes of length 1.
  • Consecutive identical characters are palindromes of length 2.
  • dp[i][j] = True indicates that s[i:j + 1] is a palindrome
  • Longer palindromes can only be formed by shorter palindromes
• Time: $O(n^2)$, space $O(n^2)$

Approach 3: Iterative

Focus on the center, and expand from it, only $O(n)$ centers to consider.

def expand(i, j):
    left = i
    right = j
 
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
 
    return right - left - 1
 
ans = [0, 0]
 
for i in range(len(s)):
    odd_length = expand(i, i)
    if odd_length > ans[1] - ans[0] + 1:
        dist = odd_length // 2
        ans = [i - dist, i + dist]
 
    even_length = expand(i, i + 1)
    if even_length > ans[1] - ans[0] + 1:
        dist = (even_length // 2) - 1
        ans = [i - dist, i + 1 + dist]
 
i, j = ans
return s[i : j + 1]

$O(n^2)$ time, but faster than approach 2 since most characters do not form a palindrome; $O(n)$ space.