Palindome

In a language of your choice write a function that takes a string and returns the longest palindrome contained in that string. A palindrome is a symmetrical string – it reads the same from left to right and from right to left. Please make sure your solution really works and provide a few interesting test cases for it. Try to make the code as efficient as you can. For extra credit provide a complexity analysis for your solution.


public class Palindome {

public static void main(String [] args){
Palindome palindome = new Palindome();
if (args.length > 0){
System.out.println("The first argument will be tested if it's palin!");
palindome.findIt(args[0]);
}else{
System.out.println("The first argument will be tested if it's palin!");
}
}

int testStringLength = 0;
String successString = null;

/*
* the main method of the algorithm, Find the length of SubStrings to be tested, starting from lagest to smallest
*/
public String findIt(String testString){
/* String testString1 = "papa I Never even get to do any things";
*/ testStringLength = testString.length();

boolean palinFound = false;
for(int i =0; i System.out.println("testString length = "+ testStringLength);
palinFound = isThereAnyPalinOfThisLength(testString, testString.length());
if(palinFound){
System.out.println("palinFound!! String successString = "+ successString);
return successString;
}
}
return successString;
}

/*
* Find all SubStrings possible of specified length.
*
*/
public boolean isThereAnyPalinOfThisLength(String testString, int testLength){
boolean b = false;
System.out.println("testString length = "+ testStringLength);
for(int i = 0; i < (testStringLength); i++){
String str = testString.substring(i, testLength);
System.out.println("Current String To Be tested : "+ str);
b = isThisPalin(str);
if(b){
successString = str;
return b;
}
}
return b;
}

/*
* This method checks whether "this exact" String is palindome or not?
*/
public boolean isThisPalin(String s){
int startPointer = 0;
int endPointer = s.length()-1;
boolean noMatch = true;
System.out.println("Is this palin = "+ s);
while(startPointer < endPointer ){
if(s.charAt(startPointer) != s.charAt(endPointer)){
noMatch = false;
break;
}
startPointer++;
endPointer--;
}
return noMatch;
}


/*
* We need to find the Largest Palindome String, We don't care if smaller Palindomes are present or not.
* Step1: Recursively find the largest to smallest strings that can be made out of the test string.
* 1a. Check whether thye whole string is palindome or not.
* 1b. If not, Check whether all Strings possible of (length-1) are palindome or not.
* 1c. If not, Check whether all Strings possible of (length-2) are palindome or not.
* 1d. continue till the time When EVEN "at least 2 characters Strings" are not Palindome:(
* Step2:
* Create all possible SubStrings of length l, and check each of them.
* Step3: check each SubString if it is palindome!
*
*
* ToDo:
* 1. Remove all special characters from the String to be tested eg All ,; $ etc. ONLY characters should remain.
* 2. When checking for character equality in isThisPalin(String s), must make sure that capital Letters and small letters are matched too!
* 3. The String should be sent from Junit test case.
*
Complexity analysis:
String length: n
Worst Case:
No of strings compared: 1(one string of length n)+2 (2 stings of length n-1)+3+.. +n
No of character comparisons: n/2; (n-1)/2...
Total char compared: n/2 + (n-1) + (n-2)....
Order of: n squared

Best Case:
No of Strings compared: 1 (The whole String is a Palindrome)
No of characters comparisons: n/2
Order of : n

Average case:
No of Strings compared: 1+2+3+ ...+ n/2
No of character comparisons: n/2; (n-1)/2...+ (n/2 -1)/2
Total char compared: n/2 + (n-1) + (n-2)....+ ((n/2-1)/2)*(n/2)
Order of: (n squared)/8