GeetCode Hub

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

int max=Int32.MinValue; string ans=""; public string LongestPalindrome(string s) { if(s.Length==0) return ans; Boolean?[,] memo=new Boolean?[s.Length,s.Length]; Traverse(s,0,s.Length-1,memo); return ans; } private bool Traverse(string s,int i,int j,Boolean?[,] memo) { if(i>j) { return true; } if(memo[i,j]!=null) return (bool)memo[i,j]; if(s[i]==s[j]&&Traverse(s,i+1,j-1,memo)) { memo[i,j]=true; if(j-i+1>max) { max=j-i+1; ans=s.Substring(i,max); } } else { memo[i,j]=false; Traverse(s,i+1,j,memo); Traverse(s,i,j-1,memo); } return (bool)memo[i,j]; }

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)

Hard