Longest Palindromic Substring 2

January 4, 2024

Problem #

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

Example:

• Input: s = "babad"
• Output: One of "bab" or "aba" (since both are valid longest palindromic substrings).

Solution #

Solution Approach #

Algorithm: Expand Around Center

This approach involves expanding around every possible center of a palindrome in the string. A palindrome can be centered around one letter (for odd length) or two letters (for even length).

Algorithm Steps: #

1. Iterate through each character in the string, treating each character as the center of a potential palindrome.
2. Expand Around Centers: For each center, expand outwards and compare characters on both sides. If they are equal, continue expanding. Otherwise, stop.
3. Track the Longest Palindrome: Keep track of the longest palindrome found during the expansion.

Python Code #

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

    if not s or len(s) < 1:
        return ""
    
    longest = ""
    for i in range(len(s)):
        # Odd length palindrome
        odd = expandAroundCenter(i, i)
        # Even length palindrome
        even = expandAroundCenter(i, i + 1)
        
        # Choose the longest one at each step
        longest = max(longest, odd, even, key=len)

    return longest

# Example Usage
s = "babad"
print(longestPalindrome(s))
# Output: "bab" or "aba"

Time Complexity: #

• O(n^2): Each expansion around a center takes O(n) time and there are O(n) centers.

Space Complexity: #

• O(1): Constant space is used irrespective of the input string size.