写一个函数，返回给定字符串中最长的回文

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).

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).

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;
}

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;
}

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;
}

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

Here is my algorithm:

1) set the current center to be the first letter

2) simultaneously expand to the left and right until you find the maximum palindrome around the current center

3) if the palindrome you find is bigger than the previous palindrome, update it

4) set the current center to be the next letter

5) repeat step 2) to 4) for all letters in the string

This runs in O(n).

Hope it helps.

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

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;
}

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.

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)

vbs

Dim strTest
wscript.echo Palindrome("abaccddccefe")

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

1. Modify string to separate each character using a separator[this is to incorporate odd and even palindromes]
2. 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;


}


}

}

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"));
}


}

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;
}
}

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<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;   }     }

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.

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

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');

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);
}
}

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 ;
}


}

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;
}

#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)

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!!");
            

}
}
    

}