3
\$\begingroup\$
import java.util.ArrayList;

import java.util.Collections;

import java.util.HashSet;

public class LargestPalindrome{
    static ArrayList<String> palinList=new ArrayList<String>();

    public static void splitString(){
        String actualString="ABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOOD";
        for(int i=0 ; i<actualString.length() ; i++){
            for(int j=i ; j<actualString.length() ; j++){
                findPalindrome(actualString.substring(i,j));    
            }
        }

    }
    public static void findPalindrome(String actualStr){    
        String reversedStr="";
        //int palindromeCount=0;

        for(int i=actualStr.length()-1 ; i>=0 ; i--){
            reversedStr+=actualStr.charAt(i);
        }

        if(actualStr.equals(reversedStr)&&actualStr.length()>=3){
            //System.out.println(actualStr);
            palinList.add(actualStr);
        }
    }


    public static String largestPalindromeCheck(ArrayList<String> palList){
        int maxLength=palList.get(0).length();
        int index=0;
        for(int i=1 ; i<palList.size() ; i++){
            if(palList.get(i).length()>maxLength){
                maxLength=palList.get(i).length();
                index=i;
            }
        }
            return palList.get(index);
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        splitString();
        //System.out.println(palinList);
        System.out.println(largestPalindromeCheck(palinList));      
    }
}

Please review the code and provide feedback on best practices and code optimization.

\$\endgroup\$
5
\$\begingroup\$

Re-organising the code

You've tried to split the logic into small functions and that was a good idea. Unfortunately, because of the way it plays with a class member palinList, the flow is quite hard to follow. In order to avoid this, the best is to define small functions that perform a simple task and return a result and to try to avoid side-effects if we don't need them.

Also, your function and argument names are not really clear. In particular :

  • splitString() : one would expect this to get a string and to return a list of string
  • actualString : what is a "non-actual" string ?
  • largestPalindromeCheck(ArrayList<String> palList) : this returns the biggest string in the list, it doesn't really matter whether this is a list of palindromes or not.

You are importing useless packages.

You should remove useless code before submitting to code review.

The style for spacing and brackets is a bit unusual.

Taking this simple comments into account (except for the last one because I can't be bothered), here's the code I have rewritten :

import java.util.ArrayList;

public class LargestPalindrome{

    public static String findLargestPalindrome(String s){
        return getLargestString(findPalindromes(s));
    }

    public static String reverseString(String s){
        String reversedStr="";
        for(int i = s.length()-1 ; i >= 0 ; i--){
            reversedStr += s.charAt(i);
        }
        return reversedStr;
    }

    public static ArrayList<String> findPalindromes(String s){
        ArrayList<String> palinList=new ArrayList<String>();
        for(int i=0 ; i<s.length() ; i++){
            for(int j=i ; j<s.length() ; j++){
                String sub = s.substring(i,j);
                if(sub.equals(reverseString(sub))&&sub.length()>=3){
                    palinList.add(sub);
                }
            }
        }
        return palinList;
    }

    public static String getLargestString(ArrayList<String> list){
        int maxLength=list.get(0).length();
        int index=0;
        for(int i=1 ; i<list.size() ; i++){
            if(list.get(i).length()>maxLength){
                maxLength=list.get(i).length();
                index=i;
            }
        }
        return list.get(index);
    }


    public static void main(String[] args) {
        String s="JUSTTOMAKETHESTRINGABITLONGERABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOODRISETOVOTESIRJUSTTOMAKETHESTRINGABITLONGERJUSTTOMAKETHESTRINGABITLONGERABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOODRISETOVOTESIRJUSTTOMAKETHESTRINGABITLONGER";
        System.out.println(findLargestPalindrome(s));
    }
}

Making things faster

if(sub.equals(reverseString(sub))&&sub.length()>=3) can be rewritten if(sub.length()>=3 && sub.equals(reverseString(sub))) to avoid going through list construction if we don't need to.

Actually, this is not so much of an issue because we can make the check for palindromes more efficient : reusing this answer, one can define a check for palindromness that doesn't need to build a string and stops as soon as the string is indeed not a palindrom. With my examples, instead of going through 2420363 iterations in reverseString(), we now perform 31423 iterations in isPalindrome.

Now, for a more dramatic improvement we have to focus on what we really want to achieve, what we are really looking for : we don't care that much about populating a list of palindromes, we only care about the biggest one. What does this imply ? It implies that we can ignore whatever is smaller than what we have already found.

At this stage, the code looks like this :

public class LargestPalindrome{

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

    public static String findLargestPalindrome(String s){
        String biggestPalindrome = "";
        for(int i=0 ; i<s.length() ; i++){
            for(int j=i ; j<s.length() ; j++){
                String sub = s.substring(i,j);
                if (sub.length()>biggestPalindrome.length() && isPalindrome(sub)){
                    biggestPalindrome = sub;
                }
            }
        }
        return biggestPalindrome;
    }

    public static void main(String[] args) {
        String s="JUSTTOMAKETHESTRINGABITLONGERABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOODRISETOVOTESIRJUSTTOMAKETHESTRINGABITLONGERJUSTTOMAKETHESTRINGABITLONGERABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOODRISETOVOTESIRJUSTTOMAKETHESTRINGABITLONGER";
        System.out.println(findLargestPalindrome(s));
    }
}

Now, an additional trick : for a given i, j will go through all values from i to s.length() -1 and the order does not really matter (yet). Thus, the loop can be returned : for(int j=i ; j<s.length() ; j++) becomes for(int j=s.length()-1 ; j >= i ; j--). First cool thing : for a given i, we'll call length() only once : it doesn't look like much but as it comes for free, it's pretty good already but the best is still to come. Indeed, for a given i, the substrings we are considering will get smaller and smaller. Thus, we can stop iterating whenever the strings we would consider become smaller than what we have found already.

This can be written :

public static String findLargestPalindrome(String s){
    String biggestPalindrome = "";
    for(int i=0 ; i<s.length() ; i++){
        for(int j=s.length()-1 ; j >= i ; j--){
            nbIt++;
            String sub = s.substring(i,j);
            if (sub.length() < biggestPalindrome.length()) break;
            if (isPalindrome(sub)){
                biggestPalindrome = sub;
            }
        }
    }
    return biggestPalindrome;
}

Actually, we don't even need to build that substring to consider its length : because of the way we construct it, sub.length() == j-i and this optimisation can be included as part of the for syntax : for(int j=s.length()-1 ; j >= i + biggestPalindrome.length(); j--).

At the end, my final version of the code looks like :

public class LargestPalindrome{

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

    public static String findLargestPalindrome(String s){
        String biggestPalindrome = "";
        for(int i=0 ; i<s.length() ; i++){
            for(int j=s.length()-1 ; j >= i + biggestPalindrome.length(); j--){
                String sub = s.substring(i,j);
                if (isPalindrome(sub)){
                    biggestPalindrome = sub;
                }
            }
        }
        return biggestPalindrome;
    }

    public static void main(String[] args) {
        String s="JUSTTOMAKETHESTRINGABITLONGERABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOODRISETOVOTESIRJUSTTOMAKETHESTRINGABITLONGERJUSTTOMAKETHESTRINGABITLONGERABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOODRISETOVOTESIRJUSTTOMAKETHESTRINGABITLONGER";
        System.out.println(findLargestPalindrome(s));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Amazing feedback!!!! \$\endgroup\$ – user3296744 Apr 3 '14 at 17:22
  • \$\begingroup\$ for(int j=s.length()-1 ; j >= i + biggestPalindrome.length(); j--){ String sub = s.substring(i,j); if (isPalindrome(sub)){ biggestPalindrome = sub; } } this portion of the code i didn't understand @Josay \$\endgroup\$ – user3296744 Apr 3 '14 at 17:31
  • \$\begingroup\$ Just like for(int j=i ; j<s.length() ; j++) makes j start from i and increase it as long as j < s.length() , for(int j=s.length()-1 ; j >= i + biggestPalindrome.length(); j--) makes j start from s.length() and decrease it as long as j >= i + biggestPalindrome.length() which basically means as long as "the string we will consider is bigger than the biggest palindrome found so far". Then the inside of the loop is nothing but extracting the substring, checking if it is a palindrome and if is it so, update the variable biggestPalindrome accordingly. \$\endgroup\$ – SylvainD Apr 4 '14 at 7:47

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.