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),

public String longestPalindrome(String s) {
if(s == null || s.length()==0){
return s;
}
int len = s.length();
boolean[][] dp = new boolean[len][len];
String lps = "";
for(int gap = 0; gap < len; gap++){
for(int i=0, j=gap; j<len;j++, i++){
if(gap==0){
dp[i][j] = true;
}
else if(gap==1){
dp[i][j] = s.charAt(i) == s.charAt(j);
}
else{
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1];
}
}
if(dp[i][j]){
lps = s.substring(i,j+1);
}
}
}
return lps;
}

We can solve this question using two approaches as discussed in the Video, in the first approach we will be using recursion with memoization while in the second approach we will be using the Dynamic Programming Tabulation approach.

Time Complexity: O(n^2)

Space Complexity: O(n^2)