Longest Palindrome - O(n^2) time and O(1) extra space
public class LongestPalindrome {
public static void main(String[] args) {
lonPal("fasxabccba");
}
public static int lonPal(String s){
int maxlen = 1;
int start = 0;
int len = s.length();
int low, high;
// for even length
for(int i = 1; i <= len; i++){
low = i;
high = i + 1;
while((low >= 0 && high < len) && (s.charAt(low) == s.charAt(high))){
if(high - low + 1 > maxlen){
start = low;
maxlen = high - low + 1;
}
--low;
++high;
}
}
// for odd length
for(int i = 1; i <= len; i++){
low = i - 1;
high = i + 1;
while((low >= 0 && high < len) && (s.charAt(low) == s.charAt(high))){
if(high - low + 1 > maxlen){
start = low;
maxlen = high - low + 1;
}
--low;
++high;
}
}
System.out.println(s.substring(start,start + maxlen));
return maxlen;
}
}
Comments
Post a Comment