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?

• 200_success: Welcome to Code Review! Please declare your cross-post to avoid wasting others' time.

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.

• maaartinus: I'd bet, he meant things like 1. N is not a good variable name according to conventions, 2. it should be more descriptive, e.g., stringCount, 3. it'd be smarter to reverse s[i] instead of s[j] as otherwise the complexity is \$N^2 \cdot L\$ where \$L\$ is the string length, etc. +++ There are many beginners here who can profit more from such step-wise advice than from a much smarter solution like yours. Sure, a complete rewrite is the way to go in this case and this makes the tiny steps irrelevant for this problem. However, it's something the OP can learn from.
• Simon Forsberg: I see nothing wrong with this answer, in any of the revisions. I'd definitely say this counts as a review.
• Simon Forsberg: A note though, there's no need to use Set.remove as Set.add will return false if it was there already.
• maaartinus: @SimonAndréForsberg Neither do I, but Quill did (in the now removed comments), so I explained what he might have meant. +++ Without Set#remove you'll get different results in case of duplicates. It's hard to tell what's right then.
• Peter Lawrey: @maaartinus thank you. This example is clearer to me. The question was cross posted on stack over flow and I believe the OP really just wanted to know how to make the code more efficient that a broad code review.

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.

• Quill: Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process.
• Peter Lawrey: Note: your choice of set will matter for performance.

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.