Write a function that returns the longest palindrome in a given string
AlgorithmPalindromeAlgorithm Problem Overview
>e.g "ccddcc" in the string "abaccddccefe"
I thought of a solution but it runs in O(n^2) time
Algo 1:
Steps: Its a brute force method
- Have 2 for loops
for i = 1 to i less than array.length -1
for j=i+1 to j less than array.length - This way you can get substring of every possible combination from the array
- Have a palindrome function which checks if a string is palindrome
- so for every substring (i,j) call this function, if it is a palindrome store it in a string variable
- If you find next palindrome substring and if it is greater than the current one, replace it with current one.
- Finally your string variable will have the answer
Issues:
- This algo runs in O(n^2) time.
Algo 2:
- Reverse the string and store it in diferent array
- Now find the largest matching substring between both the array
- But this too runs in O(n^2) time
Can you guys think of an algo which runs in a better time. If possible O(n) time
Algorithm Solutions
Solution 1 - Algorithm
You can find the the longest palindrome using Manacher's Algorithm in O(n) time! Its implementation can be found here and here.
For input String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" it finds the correct output which is 1234567887654321.
Solution 2 - Algorithm
The Algo 2 may not work for all string. Here is an example of such a string "ABCDEFCBA".
Not that the string has "ABC" and "CBA" as its substring. If you reverse the original string, it will be "ABCFEDCBA". and the longest matching substring is "ABC" which is not a palindrome.
You may need to additionally check if this longest matching substring is actually a palindrome which has the running time of O(n^3).
Solution 3 - Algorithm
As far as I understood the problem, we can find palindromes around a center index and span our search both ways, to the right and left of the center. Given that and knowing there's no palindrome on the corners of the input, we can set the boundaries to 1 and length-1. While paying attention to the minimum and maximum boundaries of the String, we verify if the characters at the positions of the symmetrical indexes (right and left) are the same for each central position till we reach our max upper bound center.
The outer loop is O(n) (max n-2 iterations), and the inner while loop is O(n) (max around (n / 2) - 1 iterations)
Here's my Java implementation using the example provided by other users.
class LongestPalindrome {
/**
* @param input is a String input
* @return The longest palindrome found in the given input.
*/
public static String getLongestPalindrome(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1; rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
leftIndex--; rightIndex++;
}
}
return longestPalindrome;
}
public static void main(String ... args) {
String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
String longestPali = getLongestPalindrome(str);
System.out.println("String: " + str);
System.out.println("Longest Palindrome: " + longestPali);
}
}
The output of this is the following:
marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
Solution 4 - Algorithm
with regex and ruby you can scan for short palindromes like this:
PROMPT> irb
>> s = "longtextwithranynarpalindrome"
=> "longtextwithranynarpalindrome"
>> s =~ /((\w)(\w)(\w)(\w)(\w)\6\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\w\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)\w\4\3\2)/; p $1
"ranynar"
=> nil
Solution 5 - Algorithm
I have written the following Java program out of curiosity, simple and self-explanatory HTH. Thanks.
/**
*
* @author sanhn
*/
public class CheckPalindrome {
private static String max_string = "";
public static void checkSubString(String s){
System.out.println("Got string is "+s);
for(int i=1;i<=s.length();i++){
StringBuilder s1 = new StringBuilder(s.substring(0,i));
StringBuilder s2 = new StringBuilder(s.substring(0,i));
s2.reverse();
if(s1.toString().equals(s2.toString())){
if(max_string.length()<=s1.length()){
max_string = s1.toString();
System.out.println("tmp max is "+max_string);
}
}
}
}
public static void main(String[] args){
String s="HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE";
for(int i=0; i<s.length(); i++)
checkSubString(s.substring(i, s.length()));
System.out.println("Max string is "+max_string);
}
}
Solution 6 - Algorithm
I was asked this question recently. Here's the solution I [eventually] came up with. I did it in JavaScript because it's pretty straightforward in that language.
The basic concept is that you walk the string looking for the smallest multi-character palindrome possible (either a two or three character one). Once you have that, expand the borders on both sides until it stops being a palindrome. If that length is longer than current longest one, store it and move along.
// This does the expanding bit.
function getsize(s, start, end) {
var count = 0, i, j;
for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
if (s[i] !== s[j]) {
return count;
}
count = j - i + 1; // keeps track of how big the palindrome is
}
return count;
}
function getBiggestPalindrome(s) {
// test for simple cases
if (s === null || s === '') { return 0; }
if (s.length === 1) { return 1; }
var longest = 1;
for (var i = 0; i < s.length - 1; i++) {
var c = s[i]; // the current letter
var l; // length of the palindrome
if (s[i] === s[i+1]) { // this is a 2 letter palindrome
l = getsize(s, i, i+1);
}
if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
l = getsize(s, i+1, i+1);
}
if (l > longest) { longest = l; }
}
return longest;
}
This could definitely be cleaned up and optimized a little more, but it should have pretty good performance in all but the worst case scenario (a string of the same letter).
Solution 7 - Algorithm
Hi Here is my code to find the longest palindrome in the string. Kindly refer to the following link to understand the algorithm http://stevekrenzel.com/articles/longest-palnidrome
Test data used is HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
//Function GetPalindromeString
public static string GetPalindromeString(string theInputString)
{
int j = 0;
int k = 0;
string aPalindrome = string.Empty;
string aLongestPalindrome = string.Empty ;
for (int i = 1; i < theInputString.Length; i++)
{
k = i + 1;
j = i - 1;
while (j >= 0 && k < theInputString.Length)
{
if (theInputString[j] != theInputString[k])
{
break;
}
else
{
j--;
k++;
}
aPalindrome = theInputString.Substring(j + 1, k - j - 1);
if (aPalindrome.Length > aLongestPalindrome.Length)
{
aLongestPalindrome = aPalindrome;
}
}
}
return aLongestPalindrome;
}
Solution 8 - Algorithm
An efficient Regexp solution which avoids brute force
Starts with the entire string length and works downwards to 2 characters, exists as soon as a match is made
For "abaccddccefe" the regexp tests 7 matches before returning ccddcc.
>(.)(.)(.)(.)(.)(.)(\6)(\5)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(.)(.)(\5)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(.)(\5)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(.)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(\3)(\2)(\1)
(.)(.)(.)(\3)(\2)(\1)
[tag:vbs]
Dim strTest
wscript.echo Palindrome("abaccddccefe")
[tag:vba]
Sub Test()
Dim strTest
MsgBox Palindrome("abaccddccefe")
End Sub
function
Function Palindrome(strIn)
Set objRegex = CreateObject("vbscript.regexp")
For lngCnt1 = Len(strIn) To 2 Step -1
lngCnt = lngCnt1 \ 2
strPal = vbNullString
For lngCnt2 = lngCnt To 1 Step -1
strPal = strPal & "(\" & lngCnt2 & ")"
Next
If lngCnt1 Mod 2 = 1 Then strPal = "(.)" & strPal
With objRegex
.Pattern = Replace(Space(lngCnt), Chr(32), "(.)") & strPal
If .Test(strIn) Then
Palindrome = .Execute(strIn)(0)
Exit For
End If
End With
Next
End Function
Solution 9 - Algorithm
See Wikipedia article on this topic. Sample Manacher's Algorithm Java implementation for linear O(n) solution from the article below:
> import java.util.Arrays; public class ManachersAlgorithm {
> public static String findLongestPalindrome(String s) {
> if (s==null || s.length()==0)
> return "";
>
> char[] s2 = addBoundaries(s.toCharArray());
> int[] p = new int[s2.length];
> int c = 0, r = 0; // Here the first element in s2 has been processed.
> int m = 0, n = 0; // The walking indices to compare if two elements are the same
> for (int i = 1; i
> char[] cs2 = new char[cs.length2+1];
> for (int i = 0; i<(cs2.length-1); i = i+2) {
> cs2[i] = '|';
> cs2[i+1] = cs[i/2];
> }
> cs2[cs2.length-1] = '|';
> return cs2; }
> private static char[] removeBoundaries(char[] cs) {
> if (cs==null || cs.length<3)
> return "".toCharArray();
>
> char[] cs2 = new char[(cs.length-1)/2];
> for (int i = 0; i
Solution 10 - Algorithm
public static void main(String[] args) {
System.out.println(longestPalindromeString("9912333321456"));
}
static public String intermediatePalindrome(String s, int left, int right) {
if (left > right) return null;
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}
public static String longestPalindromeString(String s) {
if (s == null) return null;
String longest = s.substring(0, 1);
for (int i = 0; i < s.length() - 1; i++) {
//odd cases like 121
String palindrome = intermediatePalindrome(s, i, i);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
//even cases like 1221
palindrome = intermediatePalindrome(s, i, i + 1);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
}
return longest;
}
Solution 11 - Algorithm
Try the string - "HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE"; It should work for even and odd pals. Much Thanks to Mohit!
using namespace std;
string largestPal(string input_str)
{
string isPal = "";
string largest = "";
int j, k;
for(int i = 0; i < input_str.length() - 1; ++i)
{
k = i + 1;
j = i - 1;
// starting a new interation
// check to see if even pal
if(j >= 0 && k < input_str.length()) {
if(input_str[i] == input_str[j])
j--;
else if(input_str[i] == input_str[j]) {
k++;
}
}
while(j >= 0 && k < input_str.length())
{
if(input_str[j] != input_str[k])
break;
else
{
j--;
k++;
}
isPal = input_str.substr(j + 1, k - j - 1);
if(isPal.length() > largest.length()) {
largest = isPal;
}
}
}
return largest;
}
Solution 12 - Algorithm
Following code calculates Palidrom for even length and odd length strings.
Not the best solution but works for both the cases
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE
private static String getLongestPalindrome(String string) {
String odd = getLongestPalindromeOdd(string);
String even = getLongestPalindromeEven(string);
return (odd.length() > even.length() ? odd : even);
}
public static String getLongestPalindromeOdd(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex;
rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome
.length() ? currentPalindrome : longestPalindrome;
leftIndex--;
rightIndex++;
}
}
return longestPalindrome;
}
public static String getLongestPalindromeEven(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1;
rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome
.length() ? currentPalindrome : longestPalindrome;
leftIndex--;
rightIndex++;
}
}
return longestPalindrome;
}
Solution 13 - Algorithm
- Modify string to separate each character using a separator[this is to incorporate odd and even palindromes]
- Find palindromes around each character treating it as a center
We can find all palindromes of all length using this.
Sample :
word = abcdcbc
modifiedString = a#b#c#d#c#b#c
palinCount = 1010105010301
length of longest palindrome = 5;
longest palindrome = bcdcb
public class MyLongestPalindrome {
static String word;
static int wordlength;
static int highestcount = 0;
static int newlength;
static char[] modifiedString; // stores modified string
static int[] palinCount; // stores palindrome length at each position
static char pound = '#';
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
word = bfr.readLine();
wordlength = word.length();
newlength = (wordlength * 2) - 1;
convert();
findpalindrome();
display();
}
// Inserting # in string
public static void convert() {
modifiedString = new char[newlength];
int j = 0;
int i;
for (i = 0; i < wordlength - 1; i++) {
modifiedString[j++] = word.charAt(i);
modifiedString[j++] = pound;
}
modifiedString[j] = word.charAt(i);
}
// display all palindromes of highest length
public static void display() {
String palindrome;
String s = new String(modifiedString);
System.out.println("Length of longest palindrome = " + highestcount);
for (int i = 0; i < newlength; i++) {
if (palinCount[i] == highestcount) {
palindrome = s.substring(i - (highestcount - 1), i
+ (highestcount));
i = i + (highestcount - 1);
palindrome = palindrome.replace("#", "");
System.out.println(palindrome);
}
}
}
// populate palinCount with length of palindrome string at each position
public static void findpalindrome() {
int left, right, count;
palinCount = new int[newlength];
palinCount[0] = 1;
palinCount[newlength - 1] = 1;
for (int i = 1; i < newlength - 1; i++) {
count = 0;
left = i - 1;
right = i + 1;
;
if (modifiedString[i] != pound)
count++;
while (left >= 0 && right < newlength) {
if (modifiedString[left] == modifiedString[right]) {
if (modifiedString[left] != pound)
count = count + 2;
left--;
right++;
} else
break;
}
palinCount[i] = count;
highestcount = count > highestcount ? count : highestcount;
}
}
}
Solution 14 - Algorithm
Here i have written a logic try it :)
public class palindromeClass{
public static String longestPalindromeString(String in) {
char[] input = in.toCharArray();
int longestPalindromeStart = 0;
int longestPalindromeEnd = 0;
for (int mid = 0; mid < input.length; mid++) {
// for odd palindrome case like 14341, 3 will be the mid
int left = mid-1;
int right = mid+1;
// we need to move in the left and right side by 1 place till they reach the end
while (left >= 0 && right < input.length) {
// below check to find out if its a palindrome
if (input[left] == input[right]) {
// update global indexes only if this is the longest one till now
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
// for even palindrome, we need to have similar logic with mid size 2
// for that we will start right from one extra place
left = mid;
right = mid + 1;// for example 12333321 when we choose 33 as mid
while (left >= 0 && right < input.length)
{
if (input[left] == input[right]) {
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
}
// we have the start and end indexes for longest palindrome now
return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
}
public static void main(String args[]){
System.out.println(longestPalindromeString("HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE"));
}
}
Solution 15 - Algorithm
For linear solution, you can use Manacher's algorithm. There is another algorithm call Gusfield's Algorithm, and below is the code in java:
public class Solution {
char[] temp;
public int match(int a, int b,int len){
int i = 0;
while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++;
return i;
}
public String longestPalindrome(String s) {
//This makes use of the assumption that the string has not more than 1000 characters.
temp=new char[1001*2];
int[] z=new int[1001 * 2];
int L=0, R=0;
int len=s.length();
for(int i=0;i<len*2+1;i++){
temp[i]='.';
}
for(int i=0;i<len;++i){
temp[i*2+1] = s.charAt(i);
}
z[0]=1;
len=len*2+1;
for(int i=0;i<len;i++){
int ii = L - (i - L);
int n = R + 1 - i;
if (i > R)
{
z[i] = match(i, i,len);
L = i;
R = i + z[i] - 1;
}
else if (z[ii] == n)
{
z[i] = n + match(i-n, i+n,len);
L = i;
R = i + z[i] - 1;
}
else
{
z[i] = (z[ii]<= n)? z[ii]:n;
}
}
int n = 0, p = 0;
for (int i=0; i<len; ++i)
if (z[i] > n)
n = z[p = i];
StringBuilder result=new StringBuilder();
for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)
if(temp[i]!='.')
result.append(String.valueOf(temp[i]));
return result.toString();
}
}
You can find more on other solutions such as the best O(n^2) solution or Manacher's algorithm from my own blog.
Solution 16 - Algorithm
This will return longest palindrome string from given string
-(BOOL)isPalindromString:(NSString *)strInput
{
if(strInput.length<=1){
return NO;
}
int halfLenth = (int)strInput.length/2;
BOOL isPalindrom = YES;
for(NSInteger i=0; i<halfLenth; i++){
char a = [strInput characterAtIndex:i];
char b = [strInput characterAtIndex:(strInput.length-1)-i];
if(a != b){
isPalindrom = NO;
break;
}
}
NSLog(@"-%@- IS Plaindrom %@",strInput,(isPalindrom ? @"YES" : @"NO"));
return isPalindrom;
}
-(NSString *)longestPalindrom:(NSString *)strInput
{
if(strInput.length<=1){
return @"";
}
NSString *strMaxPalindrom = @"";
for(int i = 0; i<strInput.length ; i++){
for(int j = i; j<strInput.length ; j++){
NSString *strSub = [strInput substringWithRange:NSMakeRange(i, strInput.length-j)];
if([self isPalindromString:strSub]){
if(strSub.length>strMaxPalindrom.length){
strMaxPalindrom = strSub;
}
}
}
}
NSLog(@"-Max - %@",strMaxPalindrom);
return strMaxPalindrom;
}
-(void)test
{
[self longestPalindrom:@"abcccbadeed"];
}
== OUTPUT ===
Input: abcccde Output: ccc
Input: abcccbd Output: bcccb
Input: abedccde Output: edccde
Input: abcccdeed Output: deed
Input: abcccbadeed Output: abcccba
Solution 17 - Algorithm
Here's an implementation in javascript:
var longestPalindromeLength = 0;
var longestPalindrome = ''
function isThisAPalidrome(word){
var reverse = word.split('').reverse().join('')
return word == reverse
}
function findTheLongest(word){ // takes a word of your choice
for(var i = 0; i < word.length; i++){ // iterates over each character
var wordMinusOneFromBeginning = word.substr(i, word.length) // for each letter, create the word minus the first char
for(var j = wordMinusOneFromBeginning.length; j > 0; j--){ // for the length of the word minus the first char
var wordMinusOneFromEnding = wordMinusOneFromBeginning.substr(0, j) // create a word minus the end character
if(wordMinusOneFromEnding <= 0) // make sure the value is more that 0,
continue // if more than zero, proced to next if statement
if(isThisAPalidrome(wordMinusOneFromEnding)){ // check if the word minus the first character, minus the last character = a plaindorme
if(wordMinusOneFromEnding.length > longestPalindromeLength){ // if it is
longestPalindromeLength = wordMinusOneFromEnding.length; // save its length
longestPalindrome = wordMinusOneFromEnding // and save the string itself
} // exit the statement that updates the longest palidrome
} // exit the stament that checks for a palidrome
} // exit the loop that goes backwards and takes a letter off the ending
} // exit the loop that goes forward and takes off the beginning letter
return console.log('heres the longest string: ' + longestPalindrome
+ ' its ' + longestPalindromeLength + ' charachters in length'); // return the longest palidrome! :)
}
findTheLongest('bananas');
Solution 18 - Algorithm
This Solution is of O(n^2) complexity. O(1) is the space complexity.
public class longestPalindromeInAString {
public static void main(String[] args) {
String a = "xyMADAMpRACECARwl";
String res = "";
//String longest = a.substring(0,1);
//System.out.println("longest => " +longest);
for (int i = 0; i < a.length(); i++) {
String temp = helper(a,i,i);//even palindrome
if(temp.length() > res.length()) {res = temp ;}
temp = helper(a,i,i+1);// odd length palindrome
if(temp.length() > res.length()) { res = temp ;}
}//for
System.out.println(res);
System.out.println("length of " + res + " is " + res.length());
}
private static String helper(String a, int left, int right) {
while(left>= 0 && right <= a.length() -1 && a.charAt(left) == a.charAt(right)) {
left-- ;right++ ;
}
String curr = a.substring(left + 1 , right);
System.out.println("curr =>" +curr);
return curr ;
}
}
Solution 19 - Algorithm
#longest palindrome
s='HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE'
out1=[]
def substring(x):
for i in range(len(x)):
a=x[i:]
b=x[:-i]
out1.append(a)
out1.append(b)
return out1
for i in range(len(s)):
substring(s[i:])
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]
{'DED': 3, '123456789987654321': 18, '67899876': 8, 'ABCDEDCBA': 9, '456789987654': 12, '34567899876543': 14, 'BCDEDCB': 7, 'ABA': 3, '5678998765': 10, '2345678998765432': 16, 'CDEDC': 5, '789987': 6, '8998': 4} ('123456789987654321', 18)
Solution 20 - Algorithm
Program to find the longest substring which is palindrome from a given string.
package source;
import java.util.ArrayList;
public class LongestPalindrome
{
//Check the given string is palindrome by
public static boolean isPalindrome (String s)
{
StringBuffer sb = new StringBuffer(s);
if(s.equalsIgnoreCase(sb.reverse().toString()))
return true;
else
return false;
}
public static void main(String[] args)
{
//String / word without space
String str = "MOMABCMOMOM"; // "mom" //abccbabcd
if(str.length() > 2 )
{
StringBuffer sb = new StringBuffer();
ArrayList<String> allPalindromeList = new ArrayList<>();
for(int i=0; i<str.length(); i++)
{
for(int j=i; j<str.length(); j++)
{
sb.append(str.charAt(j));
if( isPalindrome(sb.toString()) ) {
allPalindromeList.add(sb.toString());
}
}
//clear the stringBuffer
sb.delete(0, sb.length());
}
int maxSubStrLength = -1;
int indexMaxSubStr = -1;
int index = -1;
for (String subStr : allPalindromeList) {
++index;
if(maxSubStrLength < subStr.length()) {
maxSubStrLength = subStr.length();
indexMaxSubStr = index;
}
}
if(maxSubStrLength > 2)
System.out.println("Maximum Length Palindrome SubString is : "+allPalindromeList.get(indexMaxSubStr));
else
System.out.println("Not able to find a Palindrome who is three character in length!!");
}
}
}
Solution 21 - Algorithm
Here is my algorithm:
-
set the current center to be the first letter
-
simultaneously expand to the left and right until you find the maximum palindrome around the current center
-
if the palindrome you find is bigger than the previous palindrome, update it
-
set the current center to be the next letter
-
repeat step 2) to 4) for all letters in the string
This runs in O(n).
Hope it helps.
Solution 22 - Algorithm
Reference: Wikipedia.com
The best algorithm i have ever found, with complexity O(N)
import java.util.Arrays;
public class ManachersAlgorithm {
public static String findLongestPalindrome(String s) {
if (s==null || s.length()==0)
return "";
char[] s2 = addBoundaries(s.toCharArray());
int[] p = new int[s2.length];
int c = 0, r = 0; // Here the first element in s2 has been processed.
int m = 0, n = 0; // The walking indices to compare if two elements are the same
for (int i = 1; i<s2.length; i++) {
if (i>r) {
p[i] = 0; m = i-1; n = i+1;
} else {
int i2 = c*2-i;
if (p[i2]<(r-i)) {
p[i] = p[i2];
m = -1; // This signals bypassing the while loop below.
} else {
p[i] = r-i;
n = r+1; m = i*2-n;
}
}
while (m>=0 && n<s2.length && s2[m]==s2[n]) {
p[i]++; m--; n++;
}
if ((i+p[i])>r) {
c = i; r = i+p[i];
}
}
int len = 0; c = 0;
for (int i = 1; i<s2.length; i++) {
if (len<p[i]) {
len = p[i]; c = i;
}
}
char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
return String.valueOf(removeBoundaries(ss));
}
private static char[] addBoundaries(char[] cs) {
if (cs==null || cs.length==0)
return "||".toCharArray();
char[] cs2 = new char[cs.length*2+1];
for (int i = 0; i<(cs2.length-1); i = i+2) {
cs2[i] = '|';
cs2[i+1] = cs[i/2];
}
cs2[cs2.length-1] = '|';
return cs2;
}
private static char[] removeBoundaries(char[] cs) {
if (cs==null || cs.length<3)
return "".toCharArray();
char[] cs2 = new char[(cs.length-1)/2];
for (int i = 0; i<cs2.length; i++) {
cs2[i] = cs[i*2+1];
}
return cs2;
}
}
Solution 23 - Algorithm
my solution is :
static string GetPolyndrom(string str)
{
string Longest = "";
for (int i = 0; i < str.Length; i++)
{
if ((str.Length - 1 - i) < Longest.Length)
{
break;
}
for (int j = str.Length - 1; j > i; j--)
{
string str2 = str.Substring(i, j - i + 1);
if (str2.Length > Longest.Length)
{
if (str2 == str2.Reverse())
{
Longest = str2;
}
}
else
{
break;
}
}
}
return Longest;
}