Longest Palindromic Substring
Given a string `s`, return the longest palindromic substring in `s`. **Core Insight:** Expand Around Centre. A palindrome mirrors around its centre. For each character (and each pair of adjacent characters for even-length palindromes), expand outward as long as the characters on both sides match. Track the longest palindrome found. **Algorithm:** For each index `i` from 0 to n-1: expand for odd-length palindromes (centre at `i`) and even-length palindromes (centre between `i` and `i+1`). In `expand(left, right)`: while `left >= 0 && right < n && s[left] == s[right]`, decrement left and increment right. The palindrome is `s[left+1 .. right-1]`. Update the best result if this palindrome is longer. **Alternative:** Manacher's algorithm solves this in O(n) but is significantly more complex to implement. **Complexity:** Time O(n²) — n centres, each expansion up to O(n). Space O(1) extra (ignoring the output string).
Constraints
- •
1 ≤ s.length ≤ 1000
def longestPalindrome(s: str) -> str:
res = ""
for i in range(len(s)):
for l, r in [(i, i), (i, i+1)]:
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1; r += 1
return res