TestDrivenCode.comSignature
def longest_palindrome(s: str) -> str:
Test Code
# Basic test cases
assert longest_palindrome("babad") in ["bab", "aba"]
assert longest_palindrome("cbbd") == "bb"
assert longest_palindrome("") == ""
assert longest_palindrome("a") == "a"
assert longest_palindrome("ab") == "a"
assert longest_palindrome("racecar") == "racecar"
assert longest_palindrome("abcdefg") == "a"
assert longest_palindrome("forgeeksskeegfor") == "geeksskeeg"
assert longest_palindrome("abba") == "abba"
assert longest_palindrome("level!") == "level"
# Edge cases
assert longest_palindrome("aaaaa") == "aaaaa"
assert longest_palindrome("aba" + "bcdefghijklmnopqrstuvwxyz" * 4) == "aba"
assert longest_palindrome("bcdefghijklmnopqrstuvwxyz" * 4 + "aba") == "aba"
assert longest_palindrome("xayz") == "x"
assert longest_palindrome("xyz" + "a" + "bcde") == "x"
assert longest_palindrome("abccbaefg") == "abccba"
Description
Given a string s, return the longest palindromic substring in s. A palindrome is a string that reads the same forwards and backwards. If there are multiple longest palindromes, return any one of them.
Submit a Solution
Fastest Solutions
def longest_palindrome(s: str) -> str:
"""
Return the longest palindromic substring of `s`.
If there are several with the same maximum length, any one of them is returned.
"""
n = len(s)
if n < 2:
return s
# Helper to expand around a centre and return the length of the palindrome.
def expand(left: int, right: int) -> int:
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
# after the loop left/right are one step beyond the palindrome bounds
return right - left - 1 # length of palindrome
start = 0
max_len = 1
for i in range(n):
# odd length palindrome (single character centre)
len1 = expand(i, i)
# even length palindrome (centre between i and i+1)
len2 = expand(i, i + 1)
cur_len = len1 if len1 > len2 else len2
if cur_len > max_len:
# update start index based on the current centre
# cur_len = right - left - 1 => left = i - (cur_len-1)//2, right = i + cur_len//2
start = i - (cur_len - 1) // 2
max_len = cur_len
return s[start:start + max_len]
def longest_palindrome(s: str) -> str:
"""
Finds the longest palindromic substring in the given string s.
Uses the Expand Around Center approach.
"""
if not s:
return ""
start = 0
max_len = 1
def expand_around_center(left: int, right: int) -> int:
"""Expands outwards from a center point (or two center points)"""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
for i in range(len(s)):
len1 = expand_around_center(i, i)
len2 = expand_around_center(i, i + 1)
current_max_len = max(len1, len2)
if current_max_len > max_len:
max_len = current_max_len
start = i - (max_len - 1) // 2
return s[start:start + max_len]
def longest_palindrome(s: str) -> str:
if not s:
return ""
start = 0
max_len = 1
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
for i in range(len(s)):
l1 = expand(i, i)
l2 = expand(i, i+1)
cur = max(l1, l2)
if cur > max_len:
max_len = cur
start = i - (max_len - 1) // 2
return s[start:start + max_len]
New Solutions
def longest_palindrome(s: str) -> str:
if not s:
return ""
start = 0
max_len = 1
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
for i in range(len(s)):
l1 = expand(i, i)
l2 = expand(i, i+1)
cur = max(l1, l2)
if cur > max_len:
max_len = cur
start = i - (max_len - 1) // 2
return s[start:start + max_len]
def longest_palindrome(s: str) -> str:
"""
Finds the longest palindromic substring in the given string s.
Uses the Expand Around Center approach.
"""
if not s:
return ""
start = 0
max_len = 1
def expand_around_center(left: int, right: int) -> int:
"""Expands outwards from a center point (or two center points)"""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
for i in range(len(s)):
len1 = expand_around_center(i, i)
len2 = expand_around_center(i, i + 1)
current_max_len = max(len1, len2)
if current_max_len > max_len:
max_len = current_max_len
start = i - (max_len - 1) // 2
return s[start:start + max_len]
def longest_palindrome(s: str) -> str:
"""
Return the longest palindromic substring of `s`.
If there are several with the same maximum length, any one of them is returned.
"""
n = len(s)
if n < 2:
return s
# Helper to expand around a centre and return the length of the palindrome.
def expand(left: int, right: int) -> int:
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
# after the loop left/right are one step beyond the palindrome bounds
return right - left - 1 # length of palindrome
start = 0
max_len = 1
for i in range(n):
# odd length palindrome (single character centre)
len1 = expand(i, i)
# even length palindrome (centre between i and i+1)
len2 = expand(i, i + 1)
cur_len = len1 if len1 > len2 else len2
if cur_len > max_len:
# update start index based on the current centre
# cur_len = right - left - 1 => left = i - (cur_len-1)//2, right = i + cur_len//2
start = i - (cur_len - 1) // 2
max_len = cur_len
return s[start:start + max_len]