Java Program to Find The Longest Palindrome in a Given String

This post is about writing a Java program to find the longest palindrome in a given String.

Logic for finding the longest palindrome in a given string

The solution given here works on the logic that in a palindrome, starting from the center, if two cursors are moved left and right respectively one character at a time, those values should be equal. This holds true if the length of the string is odd.

For example, if string is 121 then centre is 2. Character at the left and character at the right, if checked for equality should be equal. You can check for 24642, aba, malayalam.

If the length of the string is even then you have to take 2 characters as center, and then check the character at the left and character at the right for equality. Of course two characters considered as center should be equal too.

For example, if string is 1221, then centre is 22 from there you move one character to left and one character to right. You can check for toppot, abba.

Punctuation, capitalization, and spaces are usually ignored, in the given code it is not done though.

Note that this Java program is to find the longest palindrome in the given string. For example- bananas, in this string "ana", "ana" and "anana" three palindromes are present but the longest is "anana".

If you are looking for Java program to find whether given string is palindrome or not refer this link- Check if Given String or Number is a Palindrome Java Program

Java code for finding the longest palindromic String

public class PalDemo {

  public static void main(String[] args) {
    PalDemo pd = new PalDemo();
    
    String pal = pd.findLongestPalindrome("bananas");
    System.out.println("" + pal);
    
    pal = pd.findLongestPalindrome("abaradar121");
    System.out.println("" + pal);
  }
    
  public String findLongestPalindrome(String s) {
    // Validations
    if (s.isEmpty()) {
      return "Please enter a String";
    }

    if (s.length() == 1) {
      return s;
    }
    // Validations end
    // Start with one char (starting) as a longest palindrome
    String longest = s.substring(0, 1);
    for (int i = 0; i < s.length(); i = i+1) {        
      // get longest palindrome for odd length (center is i)
      String tmp = checkForEquality(s, i, i);
      if (tmp.length() > longest.length()) {
        longest = tmp;
      }

      // get longest palindrome for even length (center is i, i+1)
      tmp = checkForEquality(s, i, i + 1);
      if (tmp.length() > longest.length()) {
        longest = tmp;
      }
    }
    return longest;
  }
    
    
  /**
  * In this method equality is checked starting from
  * the center moving one character left and one character
  * right from the center. If both chars are equal then the
  * next set of chars are checked.  
  *     
  */
  public String checkForEquality(String s, int begin, int end) {
    while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
      begin--;
      end++;
    }
    return s.substring(begin + 1, end);    
  }
}

Output

anana
radar

Let's try to have a dry run with 121 as the entered string and trace the steps-

After checking if String is empty or having just one character, first character of the string is stored as the longest.
From the for loop, in the first call to method checkForEquality() entered String is passed as the first param. Other two params begin and end will be 0 and 0.
In the while loop in the method checkForEquality(), begin >= 0 && end <= s.length() - 1 condition will pass as begin = 0 and end is less than 2 (length of string – 1). s.charAt(begin) == s.charAt(end) condition will also pass as both begin and end are pointing to same char. So begin has a value -1 and end has a value 1 now. With that while loop will fail.
Only first char of the string will be returned as s.substring(begin + 1, end) will be translated as s.substring(0, 1) for begin = -1 and end = 1.
Again checkForEquality() method will be called with 0 and 1 (this is to check for even case). With these values while loop will fail for the condition s.charAt(begin) == s.charAt(end) as both values will be different.
Now i is 1, in that case s.charAt(begin) == s.charAt(end) condition will pass as value will be 2 for both. So begin-- gives begin = 0 and end++ gives end = 2. Again s.charAt(begin) == s.charAt(end) will pass as value will be 1 for both. So begin-- gives begin = -1 and end++ gives end = 3. With these values it will come out of while loop and returns s.substring(0, 3) which is 121.
Since this returned value's length is greater than the current longest string so returned value becomes the longest.

Time complexity of the solution

Program given here to find the longest palindrome in a string in Java has a time complexity of O(N²), there is also a linear solution known as Manacher's algorithm

That's all for this topic Java Program to Find The Longest Palindrome in a Given String. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Saturday, March 11, 2023