Java Program to Find Longest Palindrome in The Given String

In this post we’ll see a Java program to find the longest palindrome in the given string. In the given string there may be more than one palindromes but you need to find which one is the longest and display that one.

For finding the longest palindrome in the string you need to start from the middle of the string and move both left and right by one character and compare those characters, if those two character are equal that means you have a palindrome and you do the same thing for the next two characters. As example in string “98189” center is 1 and by moving both left and right and comparing you can see that 8 and 8 and then 9 and 9 are equal. At the same time center of the String also moves in the program as you have to find the longest palindrome in the String.

Another thing to consider is the case when String is even, in that case you will be taking two characters as center and then do the comparison of characters. The two characters considered as center should also be equal.

Java program to find the longest palindrome

public class LongestPal {
  public static void main(String[] args) {
    LongestPal lp = new LongestPal();
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("12321981189"));
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("toppot"));
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("101312321"));
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("101311321"));
  }
	
  public String findLongestPalindrome(String str) {
    // starting point for comparison with other palindromes
    String longestPalindrome = str.substring(0, 1);
    for (int i = 0; i < str.length(); i = i+1) {  
      // odd length case (center is i)
      String newPalindrome = checkIfEqual(str, i, i);
      if (newPalindrome.length() > longestPalindrome.length()) {
        longestPalindrome = newPalindrome;
      }
      // even length case (center is i, i+1)
      newPalindrome = checkIfEqual(str, i, i + 1);
      if (newPalindrome.length() > longestPalindrome.length()) {
        longestPalindrome = newPalindrome;
      }
    }	    
    return longestPalindrome;
  }
	
  public String checkIfEqual(String str, int begin, int end) {
    while ((begin >= 0 && end <= str.length() - 1) && (str.charAt(begin) == str.charAt(end))) {
      // move left
      begin--;
      // move right
      end++;
    }
    return str.substring(begin + 1, end);    
  }
}

Output

Longest Palindrome- 981189
Longest Palindrome- toppot
Longest Palindrome- 12321
Longest Palindrome- 3113

The time complexity of this solution is O(N2) and space complexity is O(1) as the same string is used and memory requirement in the program doesn’t increase.

Related Posts

That’s all for the topic Java Program to Find Longest Palindrome in The Given String. If something is missing or you have something to share about the topic please write a comment.


You may also like

  1. Java StringBuilder With Method Examples
  2. Volatile Keyword in Java
  3. try-with-resources in Java
  4. Cannot Make a Static Reference to The Non-static Method or Field
  5. Word Count MapReduce Program in Hadoop
  6. Spring Bean Scopes

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.