Finding number of palindrome pairs in an array

Question

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?

Answer 1

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.

Answer 2

1. Make 2 sets, one for reversed strings and one for normal strings.
2. Use the retainAll() method to eliminate all the strings that aren't in both sets.
3. Return the size of the set.

Answer 3

• Uppercase variable names like N do not follow Java conventions, which is camelCase.

• N, s and str aren't too descriptive names. I'd name them number, strings and string.

• I'd simplify:

  String line = br.readLine();
  int N = Integer.parseInt(line);
  

  to:

  int number = Integer.parseInt(br.readLine());
  

• I'd not create StringBuilder sb = new StringBuilder(s[j]), which is expensive, inside loops but outside and use Java clearing the string buffer after loop.