Longest Palindrome Substring in a String in Java

Filed Under: Java

Longest palindrome substring in a string is a very common java interview question. To find out the longest palindrome in String, first of all, we need to identify the logic to do it.

Longest Palindrome Substring in a String Algorithm

The key point here is that from the mid of any palindrome string if we go to the right and left by 1 place, it’s always the same character.

For example 12321, here mid is 3 and if we keep moving one position on both sides, we get 2 and then 1. We will use the same logic in our java program to find out the longest palindrome.

However, if the palindrome length is even, the mid-size is also even. So we need to make sure in our program that this is also checked. For example, 12333321, here mid is 33 and if we keep moving one position in both sides, we get 3, 2 and 1.

Longest Palindrome Substring in a String Java Program

In our java program, we will iterate over the input string with mid as 1st place and check the right and left character.

We will have two global variables to save the start and the end position for palindrome. We also need to check if there is already a longer palindrome found since there can we multiple palindromes in the given string.

Here is the final program that works fine for all the cases.


package com.journaldev.util;

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

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

}

Below image shows the output of the above longest palindrome java program.

longest palindrome substring in a string in java

We can improve the above code by moving the palindrome and longest lengths check into a different function. However, I have left that part for you. 🙂

Please let me know if there are any other better implementations or if it fails in any case.

You can download the complete example code from our GitHub Repository.

Comments

  1. mohan says:

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

    }

  2. krissn says:

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

  3. krissn says:

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

    1. krissn says:

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

  4. Dinesh says:

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

  5. Srikanth K says:

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

    1. Shaju says:

      Try for input abacdfgdcaba

      It is returning wrong answer dcaba

  6. Anushka says:

    Thanks for this perfect code. It helped.

  7. Ranadeep Poddar says:

    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.*/

  8. Corey says:

    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.

  9. mohit kumar says:

    thanks for the code. Really helful.

  10. ANKIT SINGH says:
    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*/

    1. VJ says:

      MR Ankit, your code is not working …

      1. Ankit Singh says:

        class LongestPal
        {
        public static String rev(String s)
        {
        String s1 = “”;
        for (int i = 0; i < s.length(); i++)
        s1 = s.charAt(i) + s1;
        return s1;
        }
        public static void main(String[] args)
        {
        String s = "madamlevelnitin";
        String s1 = "";
        String s2 = "";
        String s3 = "";
        for(int i = 0; i < s.length(); i++)
        {
        for(int j = i; j < s.length(); j++)
        {
        s1 = s1 + s.charAt(j);
        s2 = rev(s1);
        s3 = s1.equals(s2) && (s3.length() <= s2.length()) ? (s3.length() 0) ? s2 : s3)) : s3;
        }
        s1 = “”;
        }
        System.out.println(“Longest Pallindrome = ” + (s3.length() > 1 ? s3 : “Not found”));
        }
        }
        /*
        ———- run ———-
        Longest Pallindrome = nitin

        Output completed (0 sec consumed) – Normal Termination
        */

  11. shravankumar says:

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

  12. prema says:

    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.

  13. Vishal says:

    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)

    1. karthikeya says:

      Your isPalindrome() method will work wrong if the length of the string is even.

  14. Ashwini Ghanghav says:

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

  15. Vivek Agrawal says:

    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))|| (
    (secondright0)&&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;
    }

    }

  16. Ellephy says:

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

    1. Vivek Agrawal says:

      a number is said to be a palindrome if that number and its reverse are equal.
      so every single digit number is palindrome.

  17. hthahseen says:

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

  18. PRASADARAO says:

    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.

  19. Rishi Chopra says:

    Hi,

    Please can you explain a bit more in detail how this has been done..

    Regards,
    Rishi Chopra.

    1. Akshay says:

      He is finding palindromes centering around all characters in the String 1 by 1. Just keeps the longest Palindrome centered at a character and then moves on the next character.

      I hope I was able to help a bit.

  20. Pankaj says:

    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.

  21. Carlos says:

    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

  22. sandeep kumar says:

    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;

    }

    }

    1. jhon says:

      private static boolean isPalindromeString(String str) {
      if (str == null)
      return false;
      int length = str.length();
      System.out.println(length / 2);
      for (int i = 0; i < length / 2; i++) {

      if (str.charAt(i) != str.charAt(length – i – 1))
      return false;
      }
      return true;
      }

      1. Anand says:

        jhon… you code perfect works and it’s simple. 🙂

        1. madhushree says:

          it just finds whether string is palindrome or not

      2. your code just searching the longest palindrome ,i mean ur code just search a single no

    2. how can u use return in main method cos in main method hv void nd u cnt return ny-thin using void

  23. abhijit says:

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

    1. NAND LAL says:

      sir plz tell me a code of java.
      Q.write a java program to add two numbers without using addition operator and utility function.
      plz reply on 12cs85@quest.edu.pk

      1. Anuj K says:

        public static int add(int a, int b){
        if(b == 0) return a;
        int sum = a ^ b; //SUM of two integer is A XOR B
        int carry = (a & b) << 1; //CARRY of two integer is A AND B
        return add(sum, carry);
        }

        1. hthahseen says:

          Your program is very perfect and it is useful to me

  24. abhijit says:

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

  25. Zhenxiang Liang says:

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

  26. Peihong says:

    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?

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages