Longest Palindrome Substring in a String in Java

Hi, Thank you for this post, but your code doesn’t work for cases like: input: abb output should be bb, but your code gives a input: bb output should be bb, but your code gives b I couldn’t figure out why? Do you think it’s possible to make your code work for these two cases?

- Peihong

Hi, I think there is two bugs in the code above. 1. when checking the mid with size 2, the original code does not check the two characters in the mid. So left should be initialized to mid and right should be initialized to mid + 1. 2. the logic of expanding left and right is not correct. In the code above, when the left and right characters are not the same, it does not end the while loop, instead it just jump over them and keep going. It should change to: while (left >= 0 && right longestRight - longestLeft){ longestLeft = left; longestRight = right; } left–; right++; }

- Zhenxiang Liang

for input 1223213 i am getting answer as 122321. Am i missing something?

- abhijit

for input 1223213 i am getting answer as 122321. Am i missing something? please reply to me at gaikwad.abhijit@gmail.com

- abhijit

package Practice; import java.util.HashSet; public class Permutationwithplaindrome { /** * @param args */ public static void main(String[] args) { String str=“abcaaa”; HashSet hset = new HashSet(); for(int i=0;i<str.length();i++){ for(int j=i+1;j0){ for(int i=0,j=str.length()-1;i<=j;i++,j–){ if(str.charAt(i)==str.charAt(j)){ continue; }else return false; } return true; } return false; } }

- sandeep kumar

This is just wrong, you are finding for pairs of letters and if you find some pair, even if the others don’t match in between that pair of letters, you accept it as a palindrome

- Carlos

Thanks for all the comments, I have found out the bug in the code and update it to work fine in all the cases it was failing before.

- Pankaj

Hi, Please can you explain a bit more in detail how this has been done… Regards, Rishi Chopra.

- Rishi Chopra

Thanks brother but it has taken some time to understand. Eventhough we are not writing 2nd if loop we are getting answer for both even and odd strings.

- PRASADARAO

Q.The sum of two number without add operator and Any other utility utility fun and the answer given by Anuj k is helpful

- hthahseen

Why is 1 palindrome in ur program? You strongly believe 1 is palin???

- Ellephy

Modified version of above code no need to call intermediatepalindrome method two times . package practice.palindrome; import java.util.ArrayList; import java.util.List; public class LongestPalindromeFinder { public static void main(String[] args) { System.out.println(longestPalindromeString(“1234”)); System.out.println(longestPalindromeString(“12321”)); System.out.println(longestPalindromeString(“9912321456”)); System.out.println(longestPalindromeString(“9912333321456”)); System.out.println(longestPalindromeString(“12145445499”)); System.out.println(longestPalindromeString(“1223213”)); System.out.println(longestPalindromeString(“abb”)); } static public List intermediatePalindrome(String s, int left, int right) { List list=new ArrayList(); int secondleft=left,secondright=right+1; if (left > right) return null; while (((left >= 0 && right < s.length())&&s.charAt(left)==s.charAt(right))|| ( (secondright~0)&&s.charAt(secondleft)==s.charAt(secondright))) { if(s.charAt(left)==s.charAt(right)) { left–; right++; } if(s.charAt(secondleft)==s.charAt(secondright)) { secondleft–; secondright++; } } list.add(s.substring(left + 1, right)); list.add(s.substring(secondleft + 1, secondright)); return list; } // O(n^2) 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 List palindromelist = intermediatePalindrome(s, i, i); for(String palindrome:palindromelist) { if (palindrome.length() > longest.length()) { longest = palindrome; } } } return longest; } }~

- Vivek Agrawal

class palindrome { public static void main(String args[]) { string original,reverse=" "; System.out.println(“Enter the String”); Scanner ash = new Scanner(System.in); original =ash.nextInt(); original =ash.nextLine(); for(int i=length-1;i>=0;i–) reverse=reverse+original.ChartAt(i); if(original.equals(reverse)) System.out.println(“enter the palindrme”); else System.out.println(“not palindrome”); } }

- Ashwini Ghanghav

Can we solve it the below way: I am getting the output correct. If not this way can you please help me what I did wrong, it will help me to code in a systematic way in future, Thanks. /* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package javaapplication15; import java.io.*; import java.util.HashSet; import java.util.*; import java.util.Set; import java.util.logging.Filter; import java.util.logging.LogRecord; /** * * @author Vishal */ public class JavaApplication15 { public static HashSet set = new HashSet(); /** * @param args the command line arguments */ public static void main(String[] args) throws Exception { ArrayList al = new ArrayList(); al.add(“ab2ba”); al.add(“abc2cba”); al.add(“abd2dba”); al.add(“wab2baw”); al.add(“lzyadb2bdayzl”); al.add(“ooab2baoo”); for (int i = 0; i < al.size(); i++) { plaindrome(al.get(i)); } } public static void plaindrome(String str) { System.out.println(str); boolean flag = true; int mid = str.length()/2; System.out.println(mid); for (int i = 1; i <= mid; i++) //*** needs to be equalto { Character char1 = str.charAt(mid+i); System.out.println(“char1=”+char1); Character char2 = str.charAt(mid-i); System.out.println(“char2=”+char2); if(!char1.equals(char2)) { flag = false; } } if(flag == true) { System.out.println(“It is a plaindrome”); set.add(str); } else { System.out.println(“It is Not a plaindrome”); } longestPlaindrome(); } public static void longestPlaindrome() { Iterator itr = set.iterator(); String temp =“”; while(itr.hasNext()) { for (int i = 0; i temp.length()) { temp = s1; } } } System.out.println(“The longest plaindrome is =”+temp); } } Output: run: ab2ba 2 char1=b char2=b char1=a char2=a It is a plaindrome ab2ba abc2cba 3 char1=c char2=c char1=b char2=b char1=a char2=a It is a plaindrome abc2cba abd2dba 3 char1=d char2=d char1=b char2=b char1=a char2=a It is a plaindrome abc2cba wab2baw 3 char1=b char2=b char1=a char2=a char1=w char2=w It is a plaindrome abc2cba lzyadb2bdayzl 6 char1=b char2=b char1=d char2=d char1=a char2=a char1=y char2=y char1=z char2=z char1=l char2=l It is a plaindrome lzyadb2bdayzl ooab2baoo 4 char1=b char2=b char1=a char2=a char1=o char2=o char1=o char2=o It is a plaindrome The longest plaindrome is =lzyadb2bdayzl BUILD SUCCESSFUL (total time: 0 seconds)

- Vishal

1223213 for this string palindrome combinations can be 22 , 232, 1 etc. But y u we r getting output only 232…could u pls fix this error i really want to know how to solve this program.

- prema

static String check(String s) { String longestPalindrome=“”; for (int i = 0; i ~=i; j–) { if (s.charAt(i) == s.charAt(j)) { String ss=s.substring(i, j+1); if(checkPalindrome(ss)) longestPalindrome=(longestPalindrome.length()<ss.length())?ss:longestPalindrome; } } } return longestPalindrome; } static boolean checkPalindrome(String s) { for (int i = 0, j = s.length() - 1; i < (s.length() / 2); i++, j–) { if (s.charAt(i) != s.charAt(j)) return false; } return true; }~

- shravankumar

class LongestPal 
{
	public static void main(String[] args) 
	{
		String s = "AAJKJAA";
		String s1 = "";
		String s2 = "";
		String longPal = "";
		for(int i = 0; i < s.length(); i++)
		{
			for(int j = i; j <s>= longPal.length() ? (s2.compareTo(longPal) > 1 ? s2 : longPal) : longPal;
			}
			s1 = "";
		}

		System.out.println(longPal.length() > 1 ? "Longest Palindrome is = " + longPal : "Not Found");
	}
	public static String rev(String s1)
	{
		String s2 = "";
		for(int i = 0; i < s1.length(); i++)
			s2 = s1.charAt(i) + s2;
		return s2;
	}
}

/* ---------- run ---------- Longest Palindrome is = AAJKJAA Output completed (0 sec consumed) - Normal Termination*/

- ANKIT SINGH

thanks for the code. Really helful.

- mohit kumar

There’s a possible Null reference exception. intermediatePalindrome will return null if (left > right). But longestPalindromeString doesn’t check if a null is returned from intermediatePalindrome before calling palindrome.length(). Admittedly I don’t see how this could occur in the given context, but it’s good form to always check your return values.

- Corey

public class LongstPalndrome { public static void main(String[] args) { String s=“abbsdsdsd”; int strlen=s.length(); outerloop: for(int i=0;i<strlen;i++) { for(int j=0;j<strlen;j++){ for (int k=0;k<=j;k++) { String l=s.substring(i+k, strlen-j+k); if(l.length()<2){ System.out.println(“No palindrome found”); break outerloop; } if(l.equals(new StringBuffer(l).reverse().toString())) { { System.out.println("The longest palindrome is “+l+” with length: "+l.length()); break outerloop; } } } } } } } /*Works.Time complexity sucks.Space is good i guess.*/

- Ranadeep Poddar

Thanks for this perfect code. It helped.

- Anushka

Just tried with my own logic. Sharing here. private static String longestPalindromeString(String string) { String p = “”; for (int i = 0; i < string.length(); i++) { String str = “”; for (int j = i; j < string.length(); j++) { str += string.charAt(j); String revStr = new StringBuilder(str).reverse().toString(); if (string.contains(revStr) && p.length() < revStr.length()) { p = revStr; } if (p.length() == string.length()) { break; } } } return p; }

- Srikanth K

this code did not pass input(contraint 10,00000) please give the efficent code

- Dinesh

String st = “abbccbba”; String out = “”; for (int i = st.length() - 1; i >= 0; i–) { out += st.charAt(i); } System.out.println(out + " is Palindrom.");

- krissn

String st = “abbccbba”; System.out.println(st + " is " + (st.equals(new StringBuilder(st).reverse().toString()) ? “Palindrom.” : “not Palindrom.”));

- krissn

Please comment on my program and let me know if I missed anything package stringprograms; public class LongestPalindrome { public static void main(String[] args) { String name = “mohanabbaganesh”; String longestPalindrome = “”; for (int i = 0; i < name.length(); ++i) { String tempString = “”; tempString = tempString + name.charAt(i); for (int j = i + 1; j longestPalindrome.length()) longestPalindrome = tempString; } } } System.out.println("longestPalindrome – " + longestPalindrome); } }

- mohan

Hi Panksj, How to find the start index of the longest palindrome in your code?

- JJ

import java.util.*; import java.lang.*; import java.io.*; class longpal { public static void main (String[] args) throws java.lang.Exception { int n=0,i,j; String s,d=" "; Scanner in=new Scanner(System.in); s=in.nextLine(); for(i=0;i<s.length()-1;i++) { for(j=i+1;jn) { n=j-i; d=s.substring(i,j); } } } System.out.print(d); } }

- Vismaya

package JAVA_Concepts; public class StringPalindrome { public Boolean checkPalindrome(String str) { StringBuilder strPal = new StringBuilder(str); // System.out.println("Original String " + strPal); // StringBuilder strRev = strPal.reverse(); StringBuilder strRev = new StringBuilder(strPal).reverse(); // System.out.println("Reversed String " + strRev.toString()); // System.out.println("Original String " + strPal.toString()); if(str.equals(strRev.toString())) { // System.out.println(“Its a Palindrome”); return true; }else { // System.out.println(“Its NOT a Palindrome”); return false; } } public Boolean interimPalindrome(String str) { String checkString = str; int lenStr = checkString.length(); // System.out.println(“Length Of String .:” + lenStr); int MaxLen = 0; int startindex = 0; int endindex = 0; boolean isPalindrome = false; for(int i=0;i<lenStr;i++) { char fnd = checkString.charAt(i); int indexofnd = checkString.indexOf(fnd); int indexofNxtfnd = checkString.indexOf(fnd, indexofnd+1); // int lastIndexoffnd = checkString.lastIndexOf(fnd); // System.out.println("FirstIndex.: " + indexofnd); while(indexofNxtfnd != -1) { // System.out.println("SecondIndex.: " + indexofNxtfnd); if((checkPalindrome(str.substring(indexofnd, indexofNxtfnd+1)))) { isPalindrome = true; if(MaxLen < str.substring(indexofnd, indexofNxtfnd+1).length()) { MaxLen = str.substring(indexofnd, indexofNxtfnd+1).length(); startindex = indexofnd; endindex = indexofNxtfnd+1; } } indexofNxtfnd = checkString.indexOf(fnd, indexofNxtfnd+1); } } if(isPalindrome) { System.out.println(“Max length Palindrome.:” + MaxLen); System.out.println(“Palindrome.:” + str.substring(startindex, endindex)); return true; }else { System.out.println(“There is No Palindrome”); return false; } } public static void main(String[] args) { // TODO Auto-generated method stub StringPalindrome onj1 = new StringPalindrome(); // System.out.println(onj1.checkPalindrome(“1234”)); onj1.interimPalindrome(“1234”); onj1.interimPalindrome(“12321”); onj1.interimPalindrome(“9912321456”); onj1.interimPalindrome(“9912333321456”); onj1.interimPalindrome(“12145445499”); onj1.interimPalindrome(“1223213”); onj1.interimPalindrome(“abb”); } }

- Satyadip Paul

For a given question to indemnify the longest palindrome in a given set of palindromes.  can you please give us more detail like if we don’t find the longest palindrome then would be ? Do we need to see for the next second longest palindrome in a given set and so on ? Please clarify this

- Mohammed

package practisesessions; public class PracticeSession { public static boolean isEmpty(String s) { return s==null || s.length()==0; } public static String reverseString(String input) { String reverse=“”; for(int count=input.length()-1;count>=0;count–) { reverse +=input.charAt(count); } return reverse; } public static String lcp(String s, String t){ int n = Math.min(s.length(),t.length()); for(int i = 0; i < n; i++){ if(s.charAt(i) != t.charAt(i)){ return s.substring(0,i); } } return s.substring(0,n); } private static boolean longestPanlindrome(String substring, String reverse) { if(reverse.indexOf(substring)!=-1) { return true; }else { return false; } } public static void main(String…strings) { String input = “adbmadamthdmaadaamssszzzzzzzzzzsum”; String reverse = reverseString(input); String longestPalindrome=“”; if(!isEmpty(input)) { for(int i=0;i<input.length();i++) { for(int j=i+1;j<=input.length();j++) { if(longestPanlindrome(input.substring(i, j),reverse)) { if(longestPalindrome.length() < (input.substring(i, j)).length()) { longestPalindrome =input.substring(i, j); } }else { break; } } } } System.out.println("Longest Palindrome is "+longestPalindrome); } }

- Suman Madyala

public static boolean isPalindrome(String strToCheck){ int mid = strToCheck.length() / 2; boolean isEven = strToCheck.length()%2==0; if (strToCheck.substring(0,mid).equals(new StringBuffer(strToCheck.substring((isEven?mid:mid+1), strToCheck.length())).reverse().toString())){ return true; } return false; }

- Chetan R

public static boolean isPalindrome(String strToCheck){ int mid=-1; if (strToCheck.length()<2 && !strToCheck.isEmpty()){ return true; } else if (!strToCheck.isEmpty()){ mid = strToCheck.length() / 2; boolean isEven = strToCheck.length()%2==0; if (strToCheck.substring(0,mid).equals(new StringBuffer(strToCheck.substring((isEven?mid:mid+1), strToCheck.length())).reverse().toString())){ return true; } } return false; }

- Chetan R