5. Longest Palindromic Substring (Medium)

Pyodide

Editor (session: default) Run

# Type here

Output Clear

Run

Editor (session: default) Run

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def expand_around_center(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        longest = ""
        for i in range(len(s)):

            # Odd length palindromes (center is s[i])
            palindrome1 = expand_around_center(i, i)
            if len(palindrome1) > len(longest):
                longest = palindrome1

            # Even length palindromes (center is s[i] and s[i+1])
            palindrome2 = expand_around_center(i, i + 1)
            if len(palindrome2) > len(longest):
                longest = palindrome2

        return longest

# --- Output Examples Code ---

print("--- Longest Palindromic Substring Examples ---")

# Create an instance of the Solution class
sol = Solution()

# Test Case 1: Odd length palindrome (bab or aba)
s1 = "babad"
result1 = sol.longestPalindrome(s1)
print(f"Input: '{s1}'")
print(f"Output: '{result1}' (Expected: 'bab' or 'aba')") 

# Test Case 2: Even length palindrome
s2 = "cbbd"
result2 = sol.longestPalindrome(s2)
print(f"Input: '{s2}'")
print(f"Output: '{result2}' (Expected: 'bb')")

# Test Case 3: Whole string is a palindrome
s3 = "racecar"
result3 = sol.longestPalindrome(s3)
print(f"Input: '{s3}'")
print(f"Output: '{result3}' (Expected: 'racecar')")

# Test Case 4: Long even length palindrome in the middle
s4 = "forgeeksskeegfor"
result4 = sol.longestPalindrome(s4)
print(f"Input: '{s4}'")
print(f"Output: '{result4}' (Expected: 'geeksskeeg')")

# Test Case 5: Single character string
s5 = "x"
result5 = sol.longestPalindrome(s5)
print(f"Input: '{s5}'")
print(f"Output: '{result5}' (Expected: 'x')")

# Test Case 6: Empty string
s6 = ""
result6 = sol.longestPalindrome(s6)
print(f"Input: '{s6}'")
print(f"Output: '{result6}' (Expected: '')")

Output Clear

Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def expand_around_center(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        longest = ""
        for i in range(len(s)):

            # Odd length palindromes (center is s[i])
            palindrome1 = expand_around_center(i, i)
            if len(palindrome1) > len(longest):
                longest = palindrome1

            # Even length palindromes (center is s[i] and s[i+1])
            palindrome2 = expand_around_center(i, i + 1)
            if len(palindrome2) > len(longest):
                longest = palindrome2

        return longest

Function Description

Source code in python/_5.py

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def expand_around_center(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        longest = ""
        for i in range(len(s)):

            # Odd length palindromes (center is s[i])
            palindrome1 = expand_around_center(i, i)
            if len(palindrome1) > len(longest):
                longest = palindrome1

            # Even length palindromes (center is s[i] and s[i+1])
            palindrome2 = expand_around_center(i, i + 1)
            if len(palindrome2) > len(longest):
                longest = palindrome2

        return longest

longestPalindrome(s)

Source code in python/_5.py

def longestPalindrome(self, s: str) -> str:

    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    longest = ""
    for i in range(len(s)):

        # Odd length palindromes (center is s[i])
        palindrome1 = expand_around_center(i, i)
        if len(palindrome1) > len(longest):
            longest = palindrome1

        # Even length palindromes (center is s[i] and s[i+1])
        palindrome2 = expand_around_center(i, i + 1)
        if len(palindrome2) > len(longest):
            longest = palindrome2

    return longest

Explanation

Given a string \(s\), the goal is to find the longest substring of \(s\) that is a palindrome. A palindrome is a sequence of characters that reads the same forwards and backwards. You can assume that the maximum length of \(s\) is 1000. If there are multiple palindromic substrings of the maximum length, any one of them can be returned as the correct answer. The challenge lies in efficiently identifying this longest substring.

The most intuitive but less efficient approach is the Brute-Force method, which checks every possible substring for the palindrome property, leading to an \(O(n^3)\) time complexity. A more optimized approach involves dynamic programming, where \(P(i, j)\) is defined as true if the substring from index \(i\) to \(j\) is a palindrome, resulting in an \(O(n^2)\) solution.

However, the most commonly discussed optimal \(O(n^2)\) solution is the Expand Around Center technique. In this method, we iterate through every possible character (and between every pair of characters) as the potential center of a palindrome. Since a palindrome can have an odd length (one center) or an even length (two centers), we check both cases and expand outwards from the center(s) as long as the characters match. This method effectively minimizes redundant checks and is often preferred for its conceptual simplicity. The most optimal solution is Manacher's Algorithm, which solves the problem in \(O(n)\) time.