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