4
\$\begingroup\$

In an array of strings 'a' having 'n' strings i have to select the Palin Pairs from the given strings .for ex for input 3 bba abb abb Output=2

I am getting correct output but want to reduce time complexity....what other logic or enhancement I can use to optimize the code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Date;

public class TestClass {


public static void main(String[] args) throws Exception {
    Date d=new Date();


     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     ArrayList<StringBuffer> al=new ArrayList<StringBuffer>();
     int count=0;
     int no=Integer.parseInt(br.readLine());
     for (int i = 0; i < no; i++) {

     String line=br.readLine();

       al.add(new StringBuffer(line));
     } 
     long ts1=System.nanoTime();
     int i=0;
     int j=0;
    for( i=0;i<al.size();i++){
        StringBuffer str=al.get(i);
        String comp=str.toString();
            for(j=i+1;j<al.size();j++){
                StringBuffer rev=al.get(j);


                String st=(rev.reverse()).toString();

                if(st.equals(comp)){
                    count++;
                }

            }
    }
    System.out.println(count);



}

}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Why don't you format your code nicely? An IDE can easily reformat it for you, for example, this is how IntelliJ reformats your code:

public class TestClass {


    public static void main(String[] args) throws Exception {
        Date d = new Date();


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<StringBuffer> al = new ArrayList<StringBuffer>();
        int count = 0;
        int no = Integer.parseInt(br.readLine());
        for (int i = 0; i < no; i++) {

            String line = br.readLine();

            al.add(new StringBuffer(line));
        }
        long ts1 = System.nanoTime();
        int i = 0;
        int j = 0;
        for (i = 0; i < al.size(); i++) {
            StringBuffer str = al.get(i);
            String comp = str.toString();
            for (j = i + 1; j < al.size(); j++) {
                StringBuffer rev = al.get(j);


                String st = (rev.reverse()).toString();

                if (st.equals(comp)) {
                    count++;
                }

            }
        }
        System.out.println(count);


    }

}

An IDE can do far more than this, for example warns of bad practices, in this code:

  • Unused variable: d,
  • new ArrayList<StringBuffer>(); can be simplified as new ArrayList<>();
  • Unused variable ts1
  • Redundant initializer int i = 0 and int j = 0

After eliminating the above, import java.util.Date also becomes unnecessary, and the code is starting to become more compact.

There remain many obvious bad practices:

  • The loop variables i and j should be declared inside the for statements: if you do that, they cannot be used outside. Which is a good thing, as they were not intended to be used outside.

  • Variables should be declared as close to where they are used as possible. Similar to the previous point, the idea is to limit mistaken uses, by minimizing the "window of vulnerability". For example, int count should be declared right before the second for loop that performs the counting.

  • ArrayList<StringBuffer> al can be declared as List<StringBuffer> al, using the interface type List instead of a specific implementation ArrayList

  • Instead of StringBuffer, it's recommended to use StringBuilder. It has exactly the same interface, so you can safely replace it everywhere in your code.

  • Avoid throwing (or catching) Exception. Try to use the most specific exception type.

  • The variable names are poor throughout. The only variable that is well-named is count. All the others could have better names.

Applying the above corrections, the program becomes much better:

public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int lineCount = Integer.parseInt(reader.readLine());

    List<StringBuilder> lines = new ArrayList<>();
    for (int i = 0; i < lineCount; i++) {
        String line = reader.readLine();
        lines.add(new StringBuilder(line));
    }

    int palindromePairCount = 0;
    for (int i = 0; i < lines.size(); i++) {
        StringBuilder str = lines.get(i);
        String comp = str.toString();
        for (int j = i + 1; j < lines.size(); j++) {
            StringBuilder rev = lines.get(j);
            String st = (rev.reverse()).toString();
            if (st.equals(comp)) {
                palindromePairCount++;
            }
        }
    }
    System.out.println(palindromePairCount);
}

We're only getting started. There are much bigger problems with the posted code, here are some tips to get you started:

  • Rework the code, replacing the List<StringBuilder> with List<String>
  • Extract the counting logic to a dedicated method that takes a List<String> and returns an int
  • Extract the palindrome checking logic to a dedicated method that takes a String and returns a boolean

These are the most obvious improvement ideas. After you implement them, more improvement opportunities will likely become apparent.

\$\endgroup\$
1
\$\begingroup\$

First of all, you declare variables d and ts1, but you never use them. You can remove those statements and also the Java.util.Date, because you never use them in the program.

Instead of calling your array al and reader br, you should change them to more descriptive titles such as input_reader and input_strings. This makes the code more readable to others.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.