2
\$\begingroup\$

The code extracts two substrings from different strings and concatinating them to provide the largest possible palindromic string.

Objective:

You have two strings, (a) and (b). Find a string, (c), such that: (c)=(d)+(e).

(d),(e) can be expressed as where (d) is a non-empty substring of (a) and (e) is a non-empty substring of (b). (c) is a palindromic string. The length of is as long as possible. For each of the pairs of strings (a) and (b) received as input, find and print string on a new line. If you're able to form more than one valid string , print whichever one comes first alphabetically. If there is no valid answer, print -1 instead.

How can I improve the performance of this code, reducing the compile time and keeping the functionality the same?

import java.io.*;
import java.util.*;

public class Solution {
    boolean isPalindrome(String s) {
  int n = s.length();
  for (int i=0;i<(n / 2);++i) {
     if (s.charAt(i) != s.charAt(n - i - 1)) {
         return false;
     }
  }

  return true;
}

    public static void main(String[] args) {

        String result="";
         Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int a=0; a<n; a++)
            {int length1, length2, i,c,d,j;
        int max_length=0;
        String string1 = in.next();
        String sub1,sub2;
        String string2 = in.next();
        length2=string2.length();
        length1 = string1.length();   

      for( c = 0 ; c <length1 ; c++ )
      {
         for( i = length1-c ; i >0 ; i-- )
         {
            sub1 = string1.substring(c, c+i);
            for( d = 0 ; d < length2 ; d++ )
      {
         for( j = length2-d ; j >0 ; j-- )
         {
            sub2 = string2.substring(d, d+j);
            String temp=sub1+sub2;
              Solution obj= new Solution();
             if(temp.length()>=max_length && obj.isPalindrome(temp)==true)

                 {
                 if (max_length==temp.length())
                  {   if(temp.compareTo(result)<0)
                     {
                     result=temp;
                  }}
                 else {
                     max_length=temp.length();
                 result=temp;
                  }
             }
         }
      }
         }
      }
             if(max_length==0)
                 System.out.println(-1);
             else
                 {
       System.out.println(result);
             result="";
             }
        }    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Do you mean execution time? \$\endgroup\$ – Jeroen Vannevel Jul 23 '16 at 21:14
  • 3
    \$\begingroup\$ "reducing the compile time" the compile time of this code is basically irrelevant. It will take longer to start the JVM used by the compiler than it will to compile this code. \$\endgroup\$ – Andy Jul 23 '16 at 22:04
1
\$\begingroup\$

Minor tweak

    boolean isPalindrome(String s) {
  int n = s.length();
  for (int i=0;i<(n / 2);++i) {
     if (s.charAt(i) != s.charAt(n - i - 1)) {
         return false;
     }
  }

Your indentation is all over the map. Copy/paste error?

More importantly, you can save some math by writing this

    public static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }

        return true;
    }

Perhaps a good compiler would optimize them out, but your original was doing four math operations per iteration where this only does two (and an extra at declaration). Not counting the comparisons for either.

Small tweak

I'd rewrite main as

        try (Scanner in = new Scanner(System.in))
        {
            for (int n = in.nextInt(); n > 0; n--)
            {
                String string1 = in.next();
                String string2 = in.next();

                String palindrome = findLongestPalindrome(string1, string2);
                if (palindrome.isEmpty())
                {
                    System.out.println(-1);
                }
                else
                {
                    System.out.println(palindrome);
                }
            }
        }

Putting the algorithm in a separate method makes it easier to test and cleans up main by a lot.

We don't need a separate loop variable for the test cases here. If we decrement instead of increment, we can simplify that logic.

Putting the Scanner in a try-with-resources eliminates a compiler warning about never closing the Scanner.

Major tweaks

      for( c = 0 ; c <length1 ; c++ )
      {
         for( i = length1-c ; i >0 ; i-- )
         {
            sub1 = string1.substring(c, c+i);
            for( d = 0 ; d < length2 ; d++ )
      {
         for( j = length2-d ; j >0 ; j-- )
         {
            sub2 = string2.substring(d, d+j);
            String temp=sub1+sub2;
              Solution obj= new Solution();
             if(temp.length()>=max_length && obj.isPalindrome(temp)==true)

                 {
                 if (max_length==temp.length())
                  {   if(temp.compareTo(result)<0)
                     {
                     result=temp;
                  }}
                 else {
                     max_length=temp.length();
                 result=temp;
                  }
             }
         }
      }
         }
      }

I changed to

    public static String findLongestPalindrome(String a, String b) {
        String result = "";
        for (int aStart = 0 ; aStart < a.length() ; aStart++ )
        {
            char firstLetter = a.charAt(aStart);
            for (int bEnd = b.lastIndexOf(firstLetter); bEnd >= 0 ; bEnd = b.lastIndexOf(firstLetter, bEnd - 1) )
            {
                for (int aEnd = a.length() ; aEnd > aStart ; aEnd-- )
                {
                    String aSubstr = a.substring(aStart, aEnd);
                    int requiredLength = Math.max(result.length() - aSubstr.length(), 0);
                    for (int bStart = 0 ; bStart <= bEnd - requiredLength; bStart++ )
                    {
                        String candidate = aSubstr + b.substring(bStart, bEnd + 1);

                        if (candidate.length() >= result.length() && isPalindrome(candidate))
                        {
                            if (candidate.length() == result.length() && candidate.compareTo(result) >= 0)
                            {
                                continue;
                            }

                            result = candidate;
                        }
                    }
                }
            }
        }

        return result;
    }

Changed arbitrary parameter names to match the problem statement.

Changed loop index variables to match their meaning relative to the parameters.

Using lastIndexOf to find the endpoint of the second string means that we can skip a lot of substrings that will never work. The original code had to take the substrings, join them, and then check if the result is a palindrome on all substrings. This reduces down to only possible substrings.

Determining the requiredLength allows us to skip joining and checking substrings that are too short to work.

I declared variables just in time to be initialized. This makes it easier to see what's happening.

An alternative algorithm

The obvious brute force solution is to check every possible start and end points for both strings. You optimized this by starting with the longest possible substrings, and I added tweaks to optimize that more. But I actually think that was the wrong way to go. Note that you still have to iterate over every letter to check if it is a palindrome. You can save checking some of the substrings if you integrate the palindrome check with taking the substrings. Instead of four nested loops with a linear time check in the middle, we can use just three nested loops. Iterate up to the correct solution rather than check down to it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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