I wrote some code to find the longest palindrome in a string (the palindrome doesn't have to appear together, as in it can be non-contiguous)
It works for almost all of the cases. For the case in code below too, it does print out the correct palindrome and it's length. However, there is this one problem that has left me confused. I have a function called compare() where I compare the length of a newly found palindrome's length with the 'longestPalindromeLength' so far, the idea being that, when all helper functions return back to main, the static(global) variable called 'longestPalindromeString' will have the result.
My problem is that, I don't see the longest palindrome, which is "ABCDEEEEDCBA" anywhere in this compare() function, when I print it.
Please see my code
public class LongestPalindromeNonContiguousPrint
{
//static String S = "abcdcba";
//static String S = "SGEGGES";
static String S = "SGEGGESABCDEEEEDCBA";
//static String S = "abca1221";
static int longestPalindromeLength = 0;
static String longestPalindromeString = "";
public static void main(String[] args)
{
System.out.println("Length of the longest palindrome == " + fun(0, S.length()-1,""));
System.out.println("Longest palindrome == "+longestPalindromeString);
}
static int fun(int s, int e, String palindrome)
{
String temp = "";
/* base cases for even */
if(s == e-1)
{
if(S.charAt(s) == S.charAt(e))
{
palindrome = palindrome + S.charAt(s);
compare(palindrome,"even");
return 2;
}
else
{
palindrome = palindrome + S.charAt(s);
compare(palindrome,"odd");
return 1;
}
}
/* base case for odd */
if(s == e)
{
palindrome = palindrome + S.charAt(s);
compare(palindrome,"odd");
return 1;
}
/*if(s > e)
return (S.charAt(s-1) == S.charAt(e+1)) ? 1:0;*/
/* recurse */
if(S.charAt(s) == S.charAt(e))
{
palindrome = palindrome + S.charAt(s);
temp = palindrome;
int rec = fun(s+1, e-1, palindrome);
palindrome = temp;
int ret = 2 + rec;
return ret;
}
else
{
temp = palindrome;
int rec1 = fun(s+1, e, palindrome);
palindrome = temp;
temp = palindrome;
int rec2 = fun(s, e-1, palindrome);
palindrome = temp;
return max(rec1, rec2);
}
}
static int max(int a, int b)
{
if(a > b)
return a;
return b;
}
static void compare(String s, String type)
{
String palindrome = "";
String rev = new StringBuilder(s).reverse().toString();
if(type == "odd")
{
palindrome = s + rev.substring(1,rev.length());
}
else if(type == "even")
{
palindrome = s + rev;
}
if(palindrome.length() > longestPalindromeLength)
{
longestPalindromeLength = palindrome.length();
longestPalindromeString = palindrome;
/* This does not get printed, I do not understand where this print() function
* sees this string ABCDEEEEDCBA */
if(longestPalindromeString == "ABCDEEEEDCBA")
{
System.out.println("found ABCDEEEEDCBA");
}
}
}
}
Output
Length of the longest palindrome == 12
Longest palindrome == ABCDEEEEDCBA
Please have a look at the compare() function, I have inserted an if-condition to print "ABCDEEEEDCBA" when that's the longest palindrome. But it never hits this condition.
EDIT : Does eclipse trim out some of the output if the output is too big. For the below program, I observe a difference in output between eclipse and running from terminal. Running on eclipse gives me 24811 lines in output, however running from the terminal gives me 47769 in output.
public class LongestPalindromeNonContiguousPrint
{
//static String S = "abcdcba";
//static String S = "GEEKSFORGEEKS";
//static String S = "SGEGGES";
static String S = "SGEGGESABCDEEEEDCBA";
//static String S = "abca1221";
static int longestPalindromeLength = 0;
static String longestPalindromeString = "";
public static void main(String[] args)
{
System.out.println("Length of the longest palindrome == " + fun(0, S.length()-1,""));
System.out.println("Longest palindrome == "+longestPalindromeString);
}
static int fun(int s, int e, String palindrome)
{
String temp = "";
/* base cases for even */
if(s == e-1)
{
if(S.charAt(s) == S.charAt(e))
{
palindrome = palindrome + S.charAt(s);
compare(palindrome,"even");
return 2;
}
else
{
palindrome = palindrome + S.charAt(s);
compare(palindrome,"odd");
return 1;
}
}
/* base case for odd */
if(s == e)
{
palindrome = palindrome + S.charAt(s);
compare(palindrome,"odd");
return 1;
}
/*if(s > e)
return (S.charAt(s-1) == S.charAt(e+1)) ? 1:0;*/
/* recurse */
if(S.charAt(s) == S.charAt(e))
{
palindrome = palindrome + S.charAt(s);
temp = palindrome;
int rec = fun(s+1, e-1, palindrome);
palindrome = temp;
int ret = 2 + rec;
return ret;
}
else
{
temp = palindrome;
int rec1 = fun(s+1, e, palindrome);
palindrome = temp;
temp = palindrome;
int rec2 = fun(s, e-1, palindrome);
palindrome = temp;
return max(rec1, rec2);
}
}
static int max(int a, int b)
{
if(a > b)
return a;
return b;
}
static void compare(String s, String type)
{
String palindrome = "";
String rev = new StringBuilder(s).reverse().toString();
if(type == "odd")
{
palindrome = s + rev.substring(1,rev.length());
}
else if(type == "even")
{
palindrome = s + rev;
}
System.out.println(palindrome);
if(palindrome.length() > longestPalindromeLength)
{
longestPalindromeLength = palindrome.length();
longestPalindromeString = palindrome;
/*if(palindrome.equals("ABCDEEEEDCBA"))
{
System.out.println("found ABCDEEEEDCBA");
}*/
}
}
}
You are comparing strings with == instead of the String's equals method.