The basic idea is to iterate through each character of the input String and expand left and right if it is a palindrome.

**Time:** *O(N^2) + O(N^2) = O(N^2)*

**Space:** *O(1)*

```
public class Solution {
public String longestPalindrome(String s) {
int N = s.length(), maxLength = -1, left = 0, right = 1;
// even length palindromes
for (int i = 1; i < N; i++) {
int j = i - 1, k = i;
while (j >= 0 && k < N && s.charAt(j) == s.charAt(k)) {
if (maxLength < k - j) {
left = j;
right = k + 1;
maxLength = k - j;
}
j--;
k++;
}
}
// odd length palindromes
for (int i = 1; i < N - 1; i++) {
int j = i - 1, k = i + 1;
while (j >= 0 && k < N && s.charAt(j) == s.charAt(k)) {
if (maxLength < k - j) {
left = j;
right = k + 1;
maxLength = k - j;
}
j--;
k++;
}
}
return s.substring(left, right);
}
}
```