Longest Palindromic Substring

Hard ⏱ 18 min 31% acceptance ★★★★★ 4.9

Write longest_palindromic_substring(s) that returns the longest contiguous substring of s that is a palindrome. If several substrings tie for the longest length, return the one that starts earliest in s.

Examples

Example 1

Input

s = 'babad'

Output

'bab'

Explanation

'bab' and 'aba' are both length-3 palindromes; 'bab' starts earlier, so it wins the tie.

Example 2

Input

s = 'cbbd'

Output

'bb'

Explanation

'bb' is the longest palindromic substring.

Constraints

1 <= len(s) <= 1000

Topics

StringsPalindromes

Companies

AmazonMicrosoftAdobe

Hints

Hint 1

Use expand-around-center for both odd and even length palindromes, from every position.

Hint 2

Track the best (start, end) span found so far, updating only on a strictly longer match to preserve the earliest tie.

← Count Palindromic Substrings One Edit Away Check →

Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.