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"
Java:
class Solution {
public String longestPalindrome(String s) {
int maxLength = 0;
int b = 0, e = 0;
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length-1; i++) {
maxLength = Math.max(Math.max(helper(cs, i, i), helper(cs, i, i+1)), maxLength);
if (e - b + 1 < maxLength) {
b = i - maxLength / 2 + 1 - maxLength % 2;
e = i + maxLength / 2;
}
}
return s.substring(b, e+1);
}
private int helper(char[] cs, int i, int j) {
int length = 0;
while(i >= 0 && j < cs.length && cs[i] == cs[j]) {
length = j - i + 1;
i--;
j++;
}
return length;
}
}
Python:
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
res = ''
for i, _ in enumerate(s):
s1 = self.helper(s, i, i)
s2 = self.helper(s, i, i+1) if i < len(s) - 1 else ''
if len(res) <= len(s1):
res = s1
if len(res) <= len(s2):
res = s2
return res
def helper(self, s, i, j):
res = ''
while i >= 0 and j < len(s) and s[i] == s[j]:
res = s[i:j+1]
i -= 1
j += 1
return res
