# Question

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

```
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
```

Example 2:

```
Input: "cbbd"
Output: "bb"
```

# Solution

Expand from center. There are \(2n-1\) centers (each character and between two characters) that the palindrome can be positioned. Check the immediate left and right character are the same, and expand from there. It gives \(O(n^2)\) time complexity and constant space complexity.

```
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) <= 1:
return s
len_s = len(s)
pali = ""
length = 0
for pos in range(0, 2 * len_s):
if pos % 2 == 0:
left, right = pos // 2, pos // 2
else:
left, right = pos // 2 + 1, pos // 2
i = 0
while left - i - 1 >= 0 and right + i + 1 < len_s and s[left-i-1] == s[right+i+1]:
i += 1
right = right + i
left = left - i
if left <= right and right - left + 1 > length:
pali = s[left:right+1]
length = right - left + 1
return pali
```