Outputs all substrings that are palindromes in a given string, in alphabetical order without repitition

Question

I'm currently trying to find a way to get my program to run more efficiently. If anyone has any ideas on how to optimize my program, i would appreciate it a lot. Also, the output has to display in alphabetic order without any duplicates.

package Palindrome;
import java.io.*;
import java.util.*;
public class Palindrome {

public static void main(String[] args)throws IOException{
    Scanner scan;   
    scan = new Scanner(System.in);
    while (scan.hasNext()) {

subPal(scan.next());
        }
    if (scan != null) {
        scan.close();
    }}


private static void subPal(String str) {
    String s1 = "";
    int N = str.length();
    ArrayList<String> palindromeArray = new ArrayList<String>();
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            int k = i + j - 1;
            if (k >= N)
            continue;
            s1 = str.substring(j, i + j);
            if (s1.equals(new StringBuilder(s1).reverse().toString())&&    !palindromeArray.contains(s1)) {
            palindromeArray.add(s1);
        }
    }

}
Collections.sort(palindromeArray);
for (String s : palindromeArray)
    System.out.println(s );

}

}

Answer 1

Performance

These are slow operations that can be replaced with faster ones:

• s1 = str.substring(j, i + j); creates new strings. A small improvement would be to use .charAt calls to access elements of str without creating copies. Another small improvement on top of that would be to convert str to a char[] using str.toCharArray() and use array indexes to access elements of the string.

• s1.equals(new StringBuilder(s1).reverse().toString()) is a lazy way to check if a string is a palindrome. It creates a new string, and then iterates over values to check if palindrome. It would be a lot better to implement a function for that, comparing pairs of letters from the beginning and end, closing in toward the center.

• !palindromeArray.contains(s1) is an \$O(n)\$ operation that can be easily turned into \$O(1)\$ by using a Set instead of an array.

• The slowest part of all is the main algorithm of enumerating possible palindromes. The nested loop basically checks all possible substring. That's not necessary. A more clever approach would be, for each position, center on the position, and keep going outward as long as the start and end letters still form a palindrome. This way you can drastically reduce the number of comparisons made in the process of checking for palindromes.

Coding style

The coding style of your post is extremely poor.

• Indentation is inconsistent, messy
• Names are poor. palindromeArray is not an "array", it's a list. And you could just call it palindromes, naturally. subPal is cryptic at best. How about printUniquePalindromes?
• It's recommended to use braces with single-statement if and for statements too.

Other issues

The scan != null condition is always true, so the if statement is unnecessary.

The initializer in String s1 = "" is redundant, String s1 would be enough

Answer 2

Code formatting

Your code is hard to read. I've seen worse, but do

• indent consistently, including ...
• avoid multiple closing braces on the same line;
• insert blank lines in appropriate places, at least
  • after the package line
  • after the imports
  • between methods (constructors);
• avoid excess blank lines

Convention

Package names should be all lowercase. Yours (Palindrome) has an initial capital letter.

Implementation / efficiency

You asked specifically about efficiency, and there are indeed several opportunities for improvement here

• avoiding duplicates

You store your palindrome substrings in a List, and avoid duplicates by testing whether that List already contains() each candidate you discover. This part is O(n²) in the number of palindromic substrings. You could instead do it in O(n) and without requiring an explicit check if you used a HashSet for palindrome storage, or in O(n log n) and without the explicit check if you used a TreeSet.

Between HashSet and TreeSet, the latter also allows you to skip the subsequent sorting, but for large numbers of elements it may be cheaper to collect elements in a HashSet and afterward dump them to a List and sort.

• palindrome search

The actual palindrome search uses an exceedingly naive -- but clear -- algorithm. For each length from 2 through the length of the string, you test each substring of that length by extracting it as a String, computing its reverse, and comparing the two.

Note first how many redundant reverses you are performing. You need only reverse the whole string, once, to obtain the reverses of all substrings.

Note second how many redundant palindrome checks you are performing. Given any palindromic substring of length greater than 3, the string obtained by removing the first and last characters is also a palindromic substring. You don't need to find all those inner ones separately if you structure your search to find the palindromic strings centered at each position.

Note also that your approach creates and discards a rather large number of temporary strings. It does this mainly because it relies on String.equals() to do its comparisons.

You could build a much more efficient approach by:

1. dumping the input string to a char[];
2. creating a separate char[] of the reversed input string; based on those arrays,
3. for each index strictly between 0 and the string length less one, finding and storing the odd-length palindromic substrings centered at that index (based on the forward and reverse arrays);
4. for each index strictly between 0 and the string length less one, find and store the even-length palindromic substrings centered between that index and the previous (based on the forward and reverse arrays).

That's still O(n²) in the worst case, but it cuts out a lot of excess temporary objects (duplicate palindromes are now the main source of unwanted temporaries), and it avoids all the unneeded reversals.

Fine details

In main(), there is no need to perform a null test on scan before closing it because there is no way scan can be null at that point.

The bounds on the inner loop of subPal() don't capture the true limits. This is evident from the fact that you compute k = i + j - 1 at the beginning of each iteration, and continue if that is too large. That's actually bad two ways: not only is the loop's termination condition deceptive, but you perform a bunch of do-nothing iterations that you could easily avoid. That is, instead of this ...

        for (int j = 0; j <= N; j++) {
            int k = i + j - 1;
            if (k >= N)
            continue;

... it would be better to simply ...

        for (int j = 0; i + j <= N; j++) {