HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Largest Palindrome Checker

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
palindromecodereviewjavastackoverflow
largestpalindromechecker

Problem

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashSet;

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

    public static void splitString(){
        String actualString="ABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOOD";
        for(int i=0 ; 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 palList){
        int maxLength=palList.get(0).length();
        int index=0;
        for(int i=1 ; imaxLength){
                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.

Solution

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 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 findPalindromes(String s){
        ArrayList palinList=new ArrayList();
        for(int i=0 ; i=3){
                    palinList.add(sub);
                }
            }
        }
        return palinList;
    }

    public static String getLargestString(ArrayList list){
        int maxLength=list.get(0).length();
        int index=0;
        for(int i=1 ; imaxLength){
                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 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= 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= i ; j--){
nbIt++;
String sub = s.substring(i,j);
if (sub.length() < biggestPalindrome.length()) break;
if (isPalindrome(sub)){
biggestPalindrome = sub;

Code Snippets

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));
    }
}
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));
    }
}
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;
}
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));
    }
}

Context

StackExchange Code Review Q#46157, answer score: 5

Revisions (0)

No revisions yet.