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)
The best known algorithm is linear time Manacher's Algorithm. Linear time with O(n) space complexity.
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
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;
}