# 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: #

**Iterate through each character**in the string, treating each character as the center of a potential palindrome.**Expand Around Centers**: For each center, expand outwards and compare characters on both sides. If they are equal, continue expanding. Otherwise, stop.**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.