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

// remember this is a substring and not a subsequence // take the odd and the even case of tthe strings lengths // start from different centers class Solution { public: string longestPalindrome(string s) { int n = s.size(); int maxlen = 1; int b = 0; int e = 0; // odd length palindromes = will have same center for(int c=0; c<n; c++){ for(int i=c,j=c; (i>=0 && j<n); i--,j++){ if(s[i]!=s[j]) break; int len = j-i+1; if(len>maxlen){ b=i; e=j; maxlen=len; } } } // even length palindromes = will have adjacent centers for(int c=0; c<n; c++){ for(int i=c,j=c+1; (i>=0 && j<n); i--,j++){ if(s[i]!=s[j]) break; int len = j-i+1; if(len>maxlen){ b=i; e=j; maxlen=len; } } } return s.substr(b,maxlen); } };

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)