Tuesday, 10 May 2016

How to find the longest palindrome in the given String - Java Program

The solution given here works on the logic that in a palindrome, starting from the centre, 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.

As 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 centre, and then check the character at the left and character at the right for equality. Of course two characters considered as centre should be equal too.

As 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 code is to find the longest palindrome in the given string as example bananas. In this string "ana", "ana" and "anana" three palindromes are present but the longest is "anana".
If you want code for - given string is palindrome or not refer this link - Check whether a given String/Number is a palindrome or not

This is a O(N2) solution, there is also a linear solution known as Manacher's algorithm

Java code for finding the longest palindrome

 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 -

  1. After checking if String is empty or having just one character, first character of the string is stored as the longest.
  2. 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.
  3. In the while loop in the method checkForEquality(), begin >= 0 && end <= s.length() - 1 part 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) wil be translated as s.substring(0, 1) for begin = -1 and end = 1.
  4. 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.
  5. 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.
  6. Since this returned value's length is greater than the current longest string so returned value becomes the longest.

That's all for this topic How to find the longest palindrome in the given String. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Check whether a given String/Number is a palindrome or not
  2. Count number of words in a String
  3. How to add double quotes to a String
  4. Print odd-even numbers using threads and semaphore
  5. Print odd-even numbers using threads and wait-notify

You may also like -

>>>Go to Java Programs page

No comments:

Post a Comment