# Largest palindrome in a string

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 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?

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

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

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.

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