Largest palindrome in a string

Question

I am working on a question in which I need to find a largest palindrome given a string. Here is the description.

public class LargestPalindrome {
  public static void main(String[] args) {
    System.out.println("Longest Palindrome 1: " +findLongestPalindrome("xyzracecar"));  
    System.out.println("Longest Palindrome 2: " +findLongestPalindrome("abcexcbaddd"));
    System.out.println("Longest Palindrome 3: " +findLongestPalindrome("cacxx"));
  }

  public static String findLongestPalindrome(String str) {
    String palindrome = ""; // initializing empty string

    for(int i=0; i<str.length(); i++) {
      for(int j = str.length(); j>i; j--) {
       String data = str.substring(i, j);
        if(isPalindrome(data)) {
          if(data.length() > palindrome.length()) {
            palindrome = data;
          }
        }
      }
    }

    return palindrome;
  }

  /**
   * This method is used to check whether a given string is palindrome or not
   * 
   */
  public static boolean isPalindrome(String s) {
    int last = s.length() - 1;

    for(int i=0; i<s.length()/2; i++) {
      if(s.charAt(i) != s.charAt(last)) {
        return false;
      }
      last--;
    }

    return true;  
  }
}

The code is working fine. Can it be optimized anymore?

Answer 1

Two minor points on the code and one on unit test:

1. Combining if clauses

   You can combine both if clauses as such:

   if (isPalindrome(current) && current.length() > palindrome.length()) { ... }
   

2. Enhancing use of for loop

   Multiple local variables can be declared in the for loop, so you can include your last variable as such:

   private static boolean isPalindrome(String s) {
       for (int i = 0, last = s.length() - 1; i < s.length() / 2; i++, last--) {
           if (s.charAt(i) != s.charAt(last)) {
               return false;
           }
       }
       return true;
   }
   

3. Unit testing

   As mentioned in my comment, it will be better to turn your main() code into a series of unit tests to ensure your logic is working correctly. The example below uses TestNG and Hamcrest matchers, and is meant to be a simple showcase for how this can be done. You should consider a variety of tests (e.g. empty Strings, non-palindromic inputs) to also ensure it works for as many cases as possible. That is when you can consider some of the features of TestNG such as parameterized testing.

   @Test
   public void doTest() {
       assertThat(findLongestPalindrome("xyzracecar"), equalTo("racecar"));
       assertThat(findLongestPalindrome("abcexcbaddd"), equalTo("ddd"));
       assertThat(findLongestPalindrome("cacxx"), equalTo("cac"));
   }
   

Bonus: Oh yeah, is it the largest or longest palindrome you are looking for? Since you are dealing with Strings, my suggestion is to be consistent and stick with permutations of 'longest palindrome'. :)

Answer 2

h.j.k.'s answer is good, but I will build on it a bit.

1. main

   As others have said, use a testing framework to test instead of this! There is nothing wrong here, it's just that testing frameworks are better and a great tool for your programming tool belt. I'd also at least add some tests for isPalindrome like assert isPalindrome("racecar") and assert !isPalindrome("foobar")

2. findLongestPalindrome

   It's true that those if clauses can be combined, but instead of combining them let's look at what's going on.

   1. We're making a substring (String data = str.substring(i, j))
   2. We're seeing if it's a palindrome (isPalindrome(data))
   3. If it's longer then we make it the one we're considering returning (if(data.length() > palindrome.length()) { palindrome = data; })

   Checking is something is a palindrome with isPalindrome is \$O(n/2)\$ which isn't terrible, but we're only saving it if it's longer than the current one we have, and we can know if it's going to be longer before we know if it's a palindrome by putting data.length() > palindrome.length() before isPalindrome(data). So long as you use && instead of & java will use short circuit evaluation and not do isPalindrome(data).

   But! An even better way is to do if (j - i > palindrome.length()) before you even make the substring and see if it's a palindrome.

3. isPalindrome

   This is fine as far as I can tell (with h.j.k.'s suggestions of course), I might consider changing last to j or i to first or something so it's consistently named.