[AMAZON]Longest palindrome substring
Given a string S, find the longest palindromic substring in S.
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
We can expand the string around its palindromic centre.There are a total of 2*n-1 palindromic centres in the string.This way all odd and even length palindromes are handled. Time complexity-O(n^2). Space complexity- O(1)
ReplyDeleteThe best known algorithm is linear time Manacher's Algorithm.
Linear time with O(n) space complexity.
static String longestPalindrome(String string){
ReplyDeleteif(string == null) return string;
if(string.length() == 1) return string;
String str = "";
for (int i = 0; i < string.length(); i++) {
str += "#" + string.charAt(i);
}
str += "#";
int[] p = new int[str.length()];
int maxIndex = -1;
int maxValue = -1;
for (int i = 0; i < str.length(); i++) {
if(i == 0) p[i] = 1;
else if(maxIndex > -1 && p[maxIndex]/2 + i > str.length()) continue;
else{
int c = 1;
for (int j = i-1, k = i+1; j >= 0 && k < str.length(); j--,k++) {
if(str.charAt(j) == str.charAt(k))
c += 2;
}
p[i] = c;
if(maxValue < c){
maxIndex = i;
maxValue = p[i];
}
}
}
str = str.substring(maxIndex-maxValue/2, maxIndex+maxValue/2+1).replaceAll("\\#", "");
return str;
}