Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Constraints:
- 1 <= s.length <= 1000
- s consist of only digits and English letters (lower-case and/or upper-case)
Examples:
Input: "babad"
Output: "bab"
Explanation: "bab" is a palindromic substring and the longest one.
Input: "cbbd"
Output: "bb"
Explanation: "bb" is a palindromic substring and the longest one.
Solutions
Expand Around Center
Time: O(n^2)Space: O(1)
The idea is to expand around the center of the palindrome. We consider two types of palindromes: odd length and even length. For odd length, the center is a single character. For even length, the center is between two characters.
def longestPalindrome(s):
longest = ''
for i in range(len(s)):
palindrome1 = expand_around_center(s, i, i)
palindrome2 = expand_around_center(s, i, i + 1)
longest = palindrome1 if len(palindrome1) > len(longest) else longest
longest = palindrome2 if len(palindrome2) > len(longest) else longest
return longest
def expand_around_center(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]Follow-up:
What if the input string is very large and we need to find all palindromic substrings?
