Given a string
s, return the longest palindromic substring in
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: s = "cbbd" Output: "bb"
Input: s = "a" Output: "a"
Input: s = "ac" Output: "a"
1 <= s.length <= 1000
sconsist of only digits and English letters (lower-case and/or upper-case),
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)