Largest palindrome in the string

Question

There are a lot similar questions out there. However, I wanted to get comments on my code. My implementation (as I believe) is simpler than the other complex ones as mine is \$O(n^2)\$.

My approach is simple:

• Start with the biggest size of string
• Check that string if its palindrome
• Reduce the string size by 1 and check each string of that size in the given string if its palindrome

I am not doing any null/size checks since I just wanted to see if my code works.

I used test data:

HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE

and it gives the correct output of:

12345678987654321

Please let me know if you have any suggestions or comments.

public static String findLargestPalindrome(String str) {
    for (int palindromeSize = str.length(); palindromeSize > 0; palindromeSize--) {
        for (int i = 0; i + palindromeSize <= str.length(); i++) {
            int substr = i + palindromeSize;
            String test;
            if (substr > str.length()) {
                test = str.substring(i);
            } else {
                test = str.substring(i, substr);
            }
            if (isPalindrome(test)) {
                return test;
            }

        }
    }
    return null;
}

public static boolean isPalindrome(String str) {
    if (str == null || str.trim().equals("")) {
        return false;
    } else if (str.length() == 1) {
        return true;
    }

    for (int i = 0, j = str.length() - 1; i <= j; i++, j--) {
        if (str.charAt(i) != str.charAt(j)) {
            return false;
        }
    }
    return true;
}

I thought about this approach by myself without looking at any of existing solutions. I haven't even read any solution except for Manacher which solves this problem in \$O(n)\$.

Answer 1

First of all: nicely programmed, organized structure and good style. But should pay attention, the way you coded it, it should be far from \$O(n^2)\$ - you can't compute isPalindrome in \$O(1)\$.

One hint for performance issues: every call of "substring" generates a new String - when you have large ones, this is getting a lot of space and time that is consumed. You could work with indices "start" and "end" and give the reference to your one string. (I mean to call something like isPalindrome("abcde", 1, 4) instead of isPalindrome("bcd")).

Dynamic Programming is now the idea to make it fully recursive, but only calculate everything once. You achieve that by building up a table and first looking up:

"have i already calculated that" ? 
    if yes -> return the value of the table without calculation (in O(1) ) 
  : if no -> calculate it and store it in the table.

Reference: click me hard

Palindromes are the classical example for dynamic programming.

Answer 2

Time complexity

It has \$O(n^2)\$ complexity.

It actually has \$O(n^3)\$ complexity. As @Cadoiz noted, isPalindrome isn't \$O(1)\$ but \$O(n)\$.

Note that Manacher's algorithm isn't \$O(n)\$ but \$O(n^2)\$. The outer for loop and the inner while loop both are \$O(n)\$. Together that makes them \$O(n^2)\$. In practice, it will do better than that, as the worst case is when every character is the same. You could also write this as \$O(m\cdot n)\$, where \$m\$ is the length of the longest palindrome substring. It's only linear if you neglect \$m\$, which is itself \$O(n)\$ in the worst case.

Manacher's is linear in space, but your version can be constant in space (if you don't make extra substrings).

Unnecessary code

        for (int i = 0; i + palindromeSize <= str.length(); i++) {
            int substr = i + palindromeSize;
            String test;
            if (substr > str.length()) {
                test = str.substring(i);
            } else {
                test = str.substring(i, substr);
            }
            if (isPalindrome(test)) {
                return test;
            }

But substr can never be greater than the length of the string, as you you check for that in the for loop test. So you can just say

         for (int i = 0; i + palindromeSize <= str.length(); i++) {
            int substr = i + palindromeSize;
            String test = str.substring(i, substr);

            if (isPalindrome(test)) {
                return test;
            }

Naming

I would generally expect something named substr to be a String, not an int. I would call this end. And to match, I'd change i to start.

I would call test something like candidate (it's not a test; it's the the thing to be tested), but I don't actually think that you need it. Consider what happens if you use Cadoiz's suggestion instead and avoid taking the substring.

         for (int start = 0, end = palindromeSize - 1; end < str.length(); start++, end++) {
            if (isPalindrome(str, start, end)) {
                return str.substring(start, end + 1);
            }
         }

Although I wouldn't be surprised if the compiler optimizes out the duplicate strings anyway.

I also changed the parameters slightly. Since we don't take the substring until we are ready to return, we don't need end to match substring. This saves us a bunch of small math operations in isPalindrome.

Work with the right data structure

Rather than work with the String, I'd probably work with the underlying character array.

    public static boolean isPalindrome(char[] characters, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (characters[i] != characters[j]) {
                return false;
            }
        }

        return true;
    }

We lose the possibility of trimming the string, but you weren't using that. It would be more efficient to do that work just once on the original string anyway.

As in your original, I assume that start and end will be reasonable values. E.g. that end will be greater than or equal to start, and both will be in range for the array. That's not hard

        if (start > end || start < 0 || end >= characters.length) {
            throw new IllegalArgumentException();
        }

but you don't have any exception handling anyway. Also note that the last two of those cases will throw more specific exceptions if you let them go through.

    public static String findLargestPalindrome(String str) {
        char [] characters = str.toCharArray();

        // start with the whole string and work down to single characters
        for (int palindromeWidth = str.length() - 1; palindromeWidth >= 0; palindromeWidth--) {
            for (int start = 0, end = palindromeWidth; end < str.length(); start++, end++) {
                if (isPalindrome(characters, start, end)) {
                    return str.substring(start, end + 1);
                }
            }
        }

        return null;
    }

This version calls isPalindrome with the character array and the starting and ending indexes.

I'm renamed palindromeSize. Note that I defined it slightly differently than you did. Hopefully the name palindromeWidth is less confusing. Perhaps a name like distance might be clearer.