# Longest Palindromic Substring

Given a string `s`, return the longest palindromic substring in `s`.

Example 1:

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

Example 2:

```Input: s = "cbbd"
Output: "bb"
```

Example 3:

```Input: s = "a"
Output: "a"
```

Example 4:

```Input: s = "ac"
Output: "a"
```

Constraints:

• `1 <= s.length <= 1000`
• `s` consist of only digits and English letters (lower-case and/or upper-case)

#### Expand Around Center

In fact, we could solve it in `O(n2)` time using only constant space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only `2n−1` such centers.

You might be asking why there are `2n−1 `but not nn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as “abba”) and its center are between the two ‘b’s.

Check the following diagram to understand that how a odd length palindrome “`pbabp`” expands around center.

```class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0){
return "";
}
String odd_length="";
String even_length ="";
String longest_palindrome ="";
for(int i = 0 ; i < s.length() ; i++){
odd_length = expandAroundCenter(s,i,i);
even_length = expandAroundCenter(s,i,i+1);
String cur_longest = odd_length.length() > even_length.length() ?
odd_length : even_length;
if(cur_longest.length() > longest_palindrome.length()){
longest_palindrome = cur_longest;
}
}
return longest_palindrome;
}

private String expandAroundCenter(String s, int l, int r){
while( l >= 0 && r < s.length()){
if(s.charAt(l) == s.charAt(r)){
l--;
r++;
}else{
break;
}
}
return s.substring(l+1, r);
}
}
```

Complexity Analysis

• Time Complexity : `O(n2)`. Since expanding a palindrome around its center could take `O(n)` time, the overall complexity is `O(n2)`.
• Space complexity : `O(1)`.

Categories: String