Tutorial

Longest Palindrome Substring in a String in Java

Published on August 3, 2022
Default avatar

By Pankaj

Longest Palindrome Substring in a String in Java

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

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.

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Learn more about us


About the authors
Default avatar
Pankaj

author

Still looking for an answer?

Ask a questionSearch for more help

Was this helpful?
 
JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
October 22, 2021

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

    JournalDev
    DigitalOcean Employee
    DigitalOcean Employee badge
    October 22, 2021

    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

      JournalDev
      DigitalOcean Employee
      DigitalOcean Employee badge
      September 23, 2021

      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

        JournalDev
        DigitalOcean Employee
        DigitalOcean Employee badge
        July 13, 2020

        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

          JournalDev
          DigitalOcean Employee
          DigitalOcean Employee badge
          March 27, 2020

          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

            JournalDev
            DigitalOcean Employee
            DigitalOcean Employee badge
            January 23, 2020

            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

              JournalDev
              DigitalOcean Employee
              DigitalOcean Employee badge
              January 13, 2020

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

              - JJ

                JournalDev
                DigitalOcean Employee
                DigitalOcean Employee badge
                November 5, 2019

                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

                  JournalDev
                  DigitalOcean Employee
                  DigitalOcean Employee badge
                  September 17, 2019

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

                  - krissn

                    JournalDev
                    DigitalOcean Employee
                    DigitalOcean Employee badge
                    September 17, 2019

                    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

                      Try DigitalOcean for free

                      Click below to sign up and get $200 of credit to try our products over 60 days!

                      Sign up

                      Join the Tech Talk
                      Success! Thank you! Please check your email for further details.

                      Please complete your information!

                      Get our biweekly newsletter

                      Sign up for Infrastructure as a Newsletter.

                      Hollie's Hub for Good

                      Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

                      Become a contributor

                      Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

                      Welcome to the developer cloud

                      DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.

                      Learn more
                      DigitalOcean Cloud Control Panel