4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Source of the challenge? \$\endgroup\$ – Legato Apr 28 '15 at 1:30
  • \$\begingroup\$ @Legato I have added it in my question. Not sure whether it can be categorized as source. Sorry for missing it earlier. \$\endgroup\$ – david Apr 28 '15 at 1:36
  • \$\begingroup\$ Quick comment: You need proper unit testing. :) \$\endgroup\$ – h.j.k. Apr 28 '15 at 2:23
2
\$\begingroup\$

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'. :)

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Good catch on doing the length check first! \$\endgroup\$ – h.j.k. Apr 29 '15 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.