Problem Statement
Explain how to find the longest palindromic substring in a string.
Explanation
Expand Around Center is the most intuitive O(n²) approach. For each character, expand outward for both odd and even length palindromes and keep track of the longest one. Dynamic programming also works with O(n²) time and space. The best optimized method, Manacher’s algorithm, finds it in O(n).
Code Solution
SolutionRead Only
String longestPalindrome(String s){
int start=0,end=0;
for(int i=0;i<s.length();i++){
int len1=expand(s,i,i);
int len2=expand(s,i,i+1);
int len=Math.max(len1,len2);
if(len>end-start){ start=i-(len-1)/2; end=i+len/2; }
}
return s.substring(start,end+1); }
int expand(String s,int l,int r){
while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){ l--; r++; }
return r-l-1; }Practice Sets
This question appears in the following practice sets:
