Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:


Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:


Input: "cbbd"
Output: "bb"

Difficulty: interview

Starter code:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        

Solutions:
class Solution(object):
     def longestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         size = len(s)
         if size <= 1 or s == s[::-1]:
             return s
         start, maxlen = 0, 1
         for idx in range(1, size):
             add2 = s[idx - maxlen - 1: idx + 1]
             if idx - maxlen - 1 >= 0 and add2 == add2[::-1]:
                 start = idx - maxlen - 1
                 maxlen += 2
                 continue
             add1 = s[idx - maxlen: idx + 1]
             if add1 == add1[::-1]:
                 start = idx - maxlen
                 maxlen += 1
         return s[start: (start + maxlen)]

class Solution:
     def longestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if not s: return ''
         maxI, center, right = 0, 0, 0
         stL = self.addChar(s)
         pal = [0] * len(stL) 
         for i in range(1, len(stL)-1):
             currI = 2 * center - i
             if right > i: pal[i] = min(right-i, pal[currI])
             else: pal[i] = 0
             while stL[i+1+pal[i]] == stL[i-1-pal[i]]:
                 pal[i] += 1
             if i+pal[i] > right: center, right = i, i+pal[i]       
         for i in range(1, len(stL)-1):
             if pal[i] > pal[maxI]: maxI = i
         start = (maxI-1-pal[maxI]) // 2
         return s[start:start+pal[maxI]]
 
     def addChar(self, st):
         stLs = ['<']
         for c in st: 
             stLs.extend([None, c])
         stLs.extend([None, '>'])
         return stLs


class Solution:
     def longestPalindrome(self, s):
         if s==s[::-1]:
             return s
         maxx=1 # itself
         start=0 # start point
         for i in range(1,len(s)):
             if i-maxx>=0 and s[i-maxx:i+1]==s[i-maxx:i+1][::-1]:
                 start=i-maxx
                 maxx+=1
                 
             elif i-maxx>=1 and s[i-maxx-1:i+1]==s[i-maxx-1:i+1][::-1]:
                 start=i-maxx-1
                 maxx+=2
         return s[start:start+maxx]


class Solution:
     def longestPalindrome(self, s):
         if s == s[::-1]:
             return s
         max_len = 1
         end = 0
         for i in range(1, len(s)):
             if i-max_len >= 0 and s[i-max_len:i+1] == s[i-max_len:i+1][::-1]:
                 max_len = max_len + 1
                 end = i
             elif i-max_len >= 1 and s[i-max_len-1:i+1] == s[i-max_len-1:i+1][::-1]:
                 max_len = max_len + 2
                 end = i
         return s[end-max_len+1:end+1]
     


class Solution:
     def longestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if len(s)==0:
         	return 0
         maxLen=1
         start=0
         for i in range(len(s)):
         	if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
         		start=i-maxLen-1
         		maxLen+=2
         		continue
 
         	if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
         		start=i-maxLen
         		maxLen+=1
         return s[start:start+maxLen]

class Solution:
     # @return a string
     def longestPalindrome(self, s):
         if len(s)==0:
         	return 0
         maxLen=1
         start=0
         for i in range(len(s)):
         	if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
         		start=i-maxLen-1
         		maxLen+=2
         		continue
 
         	if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
         		start=i-maxLen
         		maxLen+=1
         return s[start:start+maxLen]


class Solution:
     def longestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if len(s) == 0:
         	return 0
         maxLen = 1
         start = 0
         for i in range(len(s)):
         	if i - maxLen >= 1 and s[i - maxLen - 1 : i + 1] == s[i - maxLen - 1 : i + 1][:: -1]:
         		start = i - maxLen - 1
         		maxLen += 2
         		continue
 
         	if i - maxLen >= 0 and s[i - maxLen : i + 1] == s[i - maxLen : i + 1][:: -1]:
         		start = i - maxLen
         		maxLen += 1
         return s[start : start + maxLen]
         


class Solution:
     def longestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if len(s) == 0:
             return 0
         start = 0
         maxlength = 1
         for i in range(len(s)):
             if i - maxlength  - 1 >= 0 and s[i-maxlength-1:i+1] == s[i-maxlength-1:i+1][::-1]:
                 start = i-maxlength-1
                 maxlength+=2
             if i-maxlength>=0 and s[i-maxlength:i+1]==s[i-maxlength:i+1][::-1]:
                 start = i-maxlength
                 maxlength+=1
         return s[start:start+maxlength]
 


class Solution:
     def longestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if not s: return ''
         maxI, center, right = 0, 0, 0
         stL = self.addChar(s)
         pal = [0] * len(stL) 
         for i in range(1, len(stL)-1):
             currI = 2 * center - i
             if right > i: pal[i] = min(right-i, pal[currI])
             else: pal[i] = 0
             while stL[i+1+pal[i]] == stL[i-1-pal[i]]:
                 pal[i] += 1
             if i+pal[i] > right: center, right = i, i+pal[i]       
         for i in range(1, len(stL)-1):
             if pal[i] > pal[maxI]: maxI = i
         start = (maxI-1-pal[maxI]) // 2
         return s[start:start+pal[maxI]]
 
     def addChar(self, st):
         stLs = ['<']
         for c in st: 
             stLs.extend([None, c])
         stLs.extend([None, '>'])
         return stLs


class Solution:
     def longestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if not s: return ''
         maxI, center, right = 0, 0, 0
         stL = self.addChar(s)
         pal = [0] * len(stL) 
         for i in range(1, len(stL)-1):
             currI = 2 * center - i
             if right > i: pal[i] = min(right-i, pal[currI])
             else: pal[i] = 0
             while stL[i+1+pal[i]] == stL[i-1-pal[i]]:
                 pal[i] += 1
             if i+pal[i] > right: center, right = i, i+pal[i]       
         for i in range(1, len(stL)-1):
             if pal[i] > pal[maxI]: maxI = i
         start = (maxI-1-pal[maxI]) // 2
         return s[start:start+pal[maxI]]
 
     def addChar(self, st):
         stLs = ['<']
         for c in st: 
             stLs.extend(['#', c])
         stLs.extend(['#', '>'])
         return stLs