Finding number of palindrome pairs in an array

I am trying to find the number of string pairs in an array that are palindromes.

import java.io.BufferedReader;
import java.io.InputStreamReader;

class TestClass {
public static void main(String args[] ) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine();
    int N = Integer.parseInt(line);

    int count = 0;

    String s[] = new String[N];

    for (int i = 0; i < N; i++) {
        s[i] = br.readLine();                   
    }            

    for (int i = 0; i < N; i++) {
        String str = s[i];

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

            StringBuilder sb = new StringBuilder(s[j]);
            if(str.equals(sb.reverse().toString())){
                count++;
            }
        }           
    }

    System.out.print(count);
}
}

Is there a more efficient way to do this?

Is there a more efficient way to do this?

At the moment you have an \$O(N^2)\$ algorithm as you can see from the nested loops up to N This is not as efficient as it could be.

What you should have is an \$O(N \log N)\$ or \$O(N)\$ algorithm. To achieve \$O(N)\$, you need to pass over the words just once, ideally as you read them avoiding the need for a String[]. To do this, you need to store the words in a data structure with \$O(1)\$ (at least amortized) access. e.g. a HashSet or a HashMap.

It could look like this:

start with a HashSet of words so far. initially empty.
for each word *as you read it*.
   compute its palindrome.
   remove this palidrome from the set 
   and see if it was there. i.e. Set.remove(reverse) will do this.
   if it was there you have a match
   otherwise add the word to the set.
done

Instead of three loops, you only need one.

You can see that you pass over the words just once and each operation is \$O(1)\$ with the number of words. This assumes that the words length has some natural upper bound and the length of the words doesn't matter.

StackExchange Code Review Q#98018, answer score: 4