Finding largest string palindrome

Question

I've attempted to write a program to find the largest palindrome in a sentence. Spaces are included and characters are case-sensitive. Can you suggest better ways of doing this?

//public static void main(String args[])--

String source = "my malayalam is beautiful";
//Find the the largest palindrom in this sentence

StringBuilder sb = new StringBuilder( source);
String p = sb.reverse().toString();
System.out.println(p);
System.out.println(source);
int largest = 0;
try{
    for (int start=0; start <=source.length(); start++ ){
        for (int end=start+2; end < source.length(); end++){
            if (largest < (end-start)){
                String sub = source.substring(start, end);
                if (p.indexOf(sub) > 0){
                    largest = sub.length();
                    System.out.println(sub+" "+largest);
                }
            }
        }
    }
}
catch(Exception e){
    System.out.println("2");
    e.printStackTrace();
}

Answer 1

There are two things that can be criticized here: Your coding style and your algorithm.

Code Style

• There are unnecessary spaces inside some parens: new StringBuilder( source), for (…; start++ ){. Make a conscious decision to follow one style and follow it through.

• Improve readability by consistently putting a space around most operators like =, -, + and <=.

• Never ever catch (Exception e)! If there is a specific exception you would like to catch, then please do, but specify the appropriate class or interface. But often it is better to just let the exception bubble up through the call stack.

  Do not catch exceptions you are not interested in actually handling. Do not catch exceptions you have no idea where they would come from. Why are you currently catching an…

  • … ArithmeticException? Is there any chance e.g. for a division by zero in your code?
  • … ArrayIndexOutOfBoundsException? Where are you using arrays?
  • … ArrayStoreException? Where are you storing stuff into an array?
  • … ClassCastException? Your code does not contain a single cast.
  • … ClassNotFoundException? You have no dynamic class loading in your code.
  • … CloneNotSupportedException? You don't call clone on any object.
  • …

• Use good variable names that make it clear what a certain variable means. Shouldn't p be reversed or something like that?

• I would not introduce a sb variable for the StringBuilder, but rather:

  String reversed = new StringBuilder(source).reverse().toString();
  

• The palindrome finding code is not callable as a method. Extracting code into sensible methods improves testability, and can make it easier to design good programs.

Bugs

• Some bounds you choose are rather weird. For example, start <=source.length() should be start < source.length() or even better start <= source.length() - largest.

• The indexOf method returns an index on success, and -1 on failure. The snippet if (p.indexOf(sub) > 0) is therefore misleading. Anyway, you should be actually using if (p.contains(sub)).

• Your logic just asserts that the source string contains both a substring and the reversed substring. It does not assert that it contains any palindrome. For example, computers return will cause your code to output uter. You would have to check the actual indices, or better: that the substring equals itself reversed.

Algorithm

Your current algorithm works by extracting all possible substrings of length 2 or longer, and then checks whether the substring reversed is contained in the source string. As explained above, this is wrong. It is also quite inefficient, because your algorithm runs in O(n²) (two nested loops).

The problem could be solved in a fraction of the code by a recursive regular expression, e.g. in Perl/PCRE: (.)(?:(?R)|.?)\1. Sadly, the regex implementation of the Java standard library does not support this.

According to the Wikipedia article on Longest Palindromic Substrings, it is possible to find them in linear time. You may want to implement such an existing algorithm.