LeetCode Solutions Blog

Longest Palindromic Substring

Number: 5

Difficulty: Medium

Paid? No

Problem Description

Given a string s, return the longest palindromic substring in s. A palindrome is a string that reads the same forwards and backwards.

Key Insights

Every palindrome is centered around a character (for odd-length) or a pair of characters (for even-length).
Expand from each center until the substring is no longer a palindrome.
Update the longest palindrome when a longer one is found during the expansion.
The solution employs a two-pointer technique without extra storage for dynamic programming tables.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case as we expand around each center. Space Complexity: O(1), excluding the space required for the output substring.

Solution

The approach is based on expanding around potential centers of palindromes. For each character in the string, consider it as the center for an odd-length palindrome and the gap between it and the next character for an even-length palindrome. Using two pointers, expand outward until the characters differ. Track the longest palindrome found during these expansions. This method is efficient given the input constraints, and no extra data structures are needed besides variables to store indices or substrings.

Code Solutions

# Function to expand from the center and return the palindrome substring
def expand_from_center(s, left, right):
    # Expand while the characters on both sides are the same
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # Return the palindromic substring found after expansion
    return s[left + 1:right]

def longest_palindromic_substring(s):
    if not s:
        return ""
    longest = ""
    # Iterate over each index in string as potential center
    for i in range(len(s)):
        # Check for odd-length palindrome
        odd_palindrome = expand_from_center(s, i, i)
        if len(odd_palindrome) > len(longest):
            longest = odd_palindrome
        # Check for even-length palindrome
        even_palindrome = expand_from_center(s, i, i + 1)
        if len(even_palindrome) > len(longest):
            longest = even_palindrome
    return longest

# Example usage
print(longest_palindromic_substring("babad"))