# Given a string s, find the longest palindromic substring in s.
# You may assume that the maximum length of s is 1000.
#
# Example:
#
# Input: "babad"
#
# Output: "bab"
#
# Note: "aba" is also a valid answer.
#
# Example:
#
# Input: "cbbd"
#
# Output: "bb"
class Solution():
def longestPalindrome(self, s):
if len(s) == 1:
return s
longest = ""
for i in range(len(s)-1):
tmp1 = self.longestPalindromeByAxis(s, i, i)
longest = tmp1 if len(tmp1) > len(longest) else longest
tmp2 = self.longestPalindromeByAxis(s, i, i+1)
longest = tmp2 if len(tmp2) > len(longest) else longest
return longest
def longestPalindromeByAxis(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left, right = left - 1, right + 1
return s[left + 1: right]
if __name__ == "__main__":
assert Solution().longestPalindrome("a") == 'a'
assert Solution().longestPalindrome("babad") == 'bab'
assert Solution().longestPalindrome("cbbd") == 'bb'
assert Solution().longestPalindrome("VABBCBBAS") == 'ABBCBBA'