We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Palindromic Substring

Difficulty: Medium

Problem Description

Given a string s, return the longest palindromic substring in s.

Key Insights

  • A palindrome reads the same backward as forward.
  • The longest palindromic substring can be found by expanding around the center.
  • There can be two types of centers: one character (odd-length palindromes) and two characters (even-length palindromes).
  • The solution requires checking each center and expanding outwards to find the longest palindrome.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem of finding the longest palindromic substring, we can use the "expand around center" technique. This involves iterating through the string and treating each character (and each pair of characters) as a potential center of a palindrome. We expand outwards while the characters on both sides are equal. The algorithm maintains the start and end indices of the longest palindrome found during this process.

This approach effectively checks all possible palindromic substrings in O(n^2) time complexity, while using O(1) space since we only need a few variables to track indices.

Code Solutions

def longest_palindrome(s: str) -> str:
    if not s or len(s) < 1:
        return ""

    start, end = 0, 0
    
    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)   # Odd length palindrome
        len2 = expand_around_center(s, i, i + 1)  # Even length palindrome
        max_len = max(len1, len2)
        
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
            
    return s[start:end + 1]

def expand_around_center(s: str, left: int, right: int) -> int:
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1
← Back to All Questions