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

class Solution: def longestPalindrome(self, s: str) -> str: s = '#' + '#'.join(s) + '#' palidrome = '' for i in range(len(s)): l = len(self.getlongestPalidrome(s, i, i)) if l > len(palidrome): palidrome = self.getlongestPalidrome(s, i, i) return ''.join(palidrome.split('#')) def getlongestPalidrome(self, s, r, l): while l >= 0 and r < len(s) and s[r] == s[l]: l -= 1 r += 1 return s[l+1 : r]

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)