CareerCup

The logic is:
Since the palindrome can appear in any place in the long string, start with the complete string and check if it is a palindrome.
If found, we are done,
If palindrome not found, reduce string length by 1 and perform a sliding window on the input to check if it is a palindrome.
Example:
in input string "eabcbad"

String Length: 7
Longest String: "eabcbad". Result: not a palindrome.

String Length: 6
Longest String: "eabcba". Result: not a palindrome.
Longest String: "abcbad". Result: not a palindrome. (Slide the window to get next 6 character length string in the input string)

String Length: 5
Longest String: "eabcb". Result: not a palindrome.
Longest String: "abcba". Result: FOUND PALINDROME. This is the longest length palindrome.




Here is the recursive code for finding:

public class LongestPalindromeInString {

	public static void main (String[] args) {
		String input = "eabcbadd";
		
		findSubString(input, input.length(), "");
	}
	
	private static String findSubString(String str, int len, String longestPalindrome) {
		
		if(len == 1) {
			//If we reach here, that means, no palindrome found. We wont consider single characters as palindrome themselves.
			System.out.println("Palindrome longer than 1 character is not found in the input = " + str);
			return "";
		}
		
		//Since we are going from longer length to smaller length, this if is to ignore all the other recursive calls once the palindrome is found with length greater than 0
		if(len < longestPalindrome.length()) return "";
		
		boolean isPalindrome = false;
		
		for(int i=0; i<str.length()-len+1; i++) {
			isPalindrome = isPalindrome(str.substring(i, i+len));
			
			if(isPalindrome) {
				System.out.println("Longest Palindrome found in " + str + " is " + str.substring(i, i+len));
				longestPalindrome = str.substring(i, i+len);
			}
		}
		
		//recursive call to get the next set of strings by reducing length by 1
		findSubString(str, --len, longestPalindrome);
		
		return str;
	}
	
	/*This method finds if the given string is a palindrome */
	private static boolean isPalindrome (String str) {
		if(str == null || str.length() == 0) return false;
		
		int i=0; 
		int j = str.length()-1;
		while(i<j) {
			if(str.charAt(i) != str.charAt(j)) {
				return false;
			} else {
				i++;
				j--;
			}
		}
		return true;
	}
}

Here is the output of the program:

For String: "eabcbadd"
O/P: Longest Palindrome found in eabcbadd is = abcba

For String: "abcdef"
O/P: Palindrome longer than 1 character is not found in the input = abcdef

int lps(char *str, int n)
{
if (*str==*(str+n))
return 1;
if (*str == *(str+n) && strlen(str)==2)
return 2;
if (*str == *(str+n))
return lps (*(str+1), n-1) + 2;
return max( lps(*str, n-1), lps(*(str+1), n) );
}

I came up with a solution without recursion. It takes O(n^2) time.

#include<stdio.h>
int LPS(char *s,int n);
int main()
{
	char array[100];
	char c;
	int i = 0;
	c = getchar();
	while(c!='\n')
	{
		array[i++]=c;
		c = getchar();
	}
	array[i] ='\0';
	int n = i;
	int l = LPS(array,n);
	printf("%d\n",l);
	return 0;
}
int LPS(char *s,int n)
{
	int x = 0;
	int i ,k = 2;
	int count = 1;
	int max = -500;
	int j = 0;
	for(i=1;i<n-1;i++)
	{
		if(s[j]==s[k] && j>=0 && k<=n-1)
		{
			count += 2;
			j--;
			k++;
			i--;
			if(count > max)
			{
				max = count;
			}
			if(j<0)
			{
				count = 1;
				i = k-2;
				j = i;
			}
		}
		else if(s[k]==s[i])
		{
			count += 1;
			k++;
			i--;
			if(count > max)
			{
				max = count;
			}
		}
		else
		{	
			k++;
			i = k-2;
			j = i;
			count = 1;
		}
	}	
	if(count>max)
	{
		max = count;
	}
	return max;
}

def longestPalindromeRecursive(s):
    if isPalindrome(s):
        return s
    return max([longestPalindromeRecursive(s[1:])] + [longestPalindromeRecursive(s[:-1])], key=len)

def isPalindrome(s):
    for i in range(len(s) / 2):
        if s[i] != s[-i-1]:
            return False
    return True

print longestPalindromeRecursive("aabazzzz")

With better formatting (python):

def LPS(s):
    if isPalindrome(s):
        return s
    return max([LPS(s[1:])] + [LPS(s[:-1])], key=len)

def isPalindrome(s):
    for i in range(len(s) / 2):
        if s[i] != s[-i-1]:
            return False
    return True

print LPS("aabazzzzazzz")

I think my code will works and I use Manacher's algorithm. For more information, search this algorithm and you will know how it works.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;

class LGSTPalinddromeFinder
{
public:
    string longestPalindrome(string s)
    {
        size_t n = s.length();
        if(n<=1)
        {
            return s;
        }
        
        string ms = "$#";
        for(int i=0; i<n; i++)
        {
            ms.append(1, s[i]);
            ms.append(1, '#');
        }
        
        int m = (int)n*2+2;
        vector<int> pa(m, 0);
        
        int maxi=0, id=0, mi = id+pa[id];
        
        for(int i=1; i<m-1; i++)
        {
            if(i >= mi)
            {
                pa[i] = 0;
            }
            else
            {
                if(pa[2*id-i] < pa[id]+id-i)
                {
                    pa[i] = pa[2*id-i];
                    continue;
                }
                else
                {
                    pa[i] = pa[id]+id-i;
                }
            }
            
			
			while(ms[i-pa[i]-1] == ms[i+pa[i]+1])
			{
				pa[i]++;
				if((i+pa[i]+1) >= ms.size())
				{
					break;
				}
			}
            
            if(i+pa[i]>mi)
            {
                id = i;
                mi = id + pa[id];
            }
            
            if(pa[i]>pa[maxi])
            {
                maxi = i;
            }
        }
        
        string r;
        int left = maxi - pa[maxi], right = maxi + pa[maxi];
        
        for(int i = left; i<=right; i++)
        {
            if(ms[i] != '$' && ms[i] != '#')
                r.append(1, ms[i]);
        }
        
        return r;
        
    }
};

int main(int argc, const char * argv[])
{
    

    
    // insert code here...
    string s;
    cin >> s;
    LGSTPalinddromeFinder so;
    string r = so.longestPalindrome(s);
    cout<<r<<endl;
    return 0;
}

Can we reverse the string and find LCS of reverse string and original string ??

#include <stdio.h>
#include <stdlib.h>

int LPS(char *str, int N)
{
    int i;
    int l=0;
    int l1=0;
    int l2=0;

    if (N<=1)
        return 1;
    if(str[0] == str[N-1])
    {
        l=1;
        while(i < (N-1-i))
        {

            if(str[i] != str[N-1-i])
            {
                l=0;
                break;
            }
            i++;
        }

    }
    if (l>0)
        return N-1;
    l1=LPS(str+1,N-1);
    l2=LPS(str,N-1);

   return (l1>l2?l1:l2);
}



int main()
{
    char str[]="aasaaddsdsddsg";
    printf("length %d\n",LPS(str,14));
return 0;
}

#include <stdio.h>
#include <stdlib.h>

int LPS(char *str, int N)
{
    int i=0;
    int l=0;
    int l1=0;
    int l2=0;

    if (N<=1)
        return 1;
    if(str[0] == str[N-1])
    {
        l=1;
        while(i < (N-1-i))
        {

            if(str[i] != str[N-1-i])
            {
                l=0;
                break;
            }
            i++;
        }

    }
    if (l!=0)
        return (N%2 == 0)? 2*i : 2*i+1;
    l1=LPS(str+1,N-1);
    l2=LPS(str,N-1);

   return (l1>l2?l1:l2);
}



int main()
{
    char str[]="xabccbav";
    printf("length %d\n",LPS(str,8));
return 0;
}

#include <iostream>

bool
isPalindrome(const std::string& input) {
  for( int i=0, j=input.length()-1; i<j; i++,j--) {
    if(input[i] != input[j]) {
      return false;
    }
  }
  return true;
}

std::string
LPS(const std::string& input) {
  if(input.length() < 2 ) {
    return "";
  }
  
  if(isPalindrome(input)) {
    return input;
  }
  
  std::string leftLps = LPS(input.substr(1,input.length()-1));
  std::string rightLps = LPS(input.substr(0,input.length()-1));
  
  if(leftLps.length() > rightLps.length()) {
    return leftLps;
  }
  else {
    return rightLps;
  }
  
}

/* Driver Program */

int 
main(int argc, char **argv) {
  std::string input;
  std::cin >> input;
  std::cout << LPS(input);
  
  return 0;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int max(int a, int b){
	if (a>b) return a;
	else return b;
}

//39eabajdk3kabbbajdhjcjcjcj
int LPS(char *str1, int n){
	if (n == 0) return 0;
	int i = 0;
	int j = n - 1;
	int p_len = 0;
	int max_len = 0;
	while (j > 0){
		if (str1[i] == str1[j]){
			if (i == j || j == i+1) {
				p_len++;
				if (p_len > max_len){
					max_len = p_len;
					break;
				}
			}
			else {
				p_len += 2;
			}
			i++;
			j--;
		}
		else{
			i = 0;
			p_len = 0;
			j--;
		}

	}
	//printf("str1 is %s, max_len is %d\n", str1, max_len);
	return max(max_len, LPS(str1+1, n-1));

}
	
int main() {
	char *str1 = "39eabajdk3kabbbajdhjcjcjcj";
	printf("max LPS is %d\n", LPS(str1, strlen(str1)));
}

str="abcdefghgfedcba"
l=len(str)-1
i=0
def getcn(str,i,j):
while i<j:
if str[i]!=str[j]:
return 'n'
i+=1
j-=1
return 'y'
def checkP(str,i,l):
if i>=l:
list1=[0,0]
return list1
else:
list1=checkP(str,i+1,l)
if (l-i)>(list1[1]-list1[0]):
for m in range(l,i,-1):
if str[i]==str[m]:
y=getcn(str,i,m)
if y=='y':
if (m-i)>(list1[1]-list1[0]):
list1=[i,m]
return list1
list1=checkP(str,i,l)
if list1[0]==list1[1]:
print "No pallindrome"
else:
for i in range(list1[0],list1[1]+1):
print str[i],

Best case: O(1)
otherwise: O(n*n)

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string ss;
void LSP(string s, int i, int length, int n){

ss = "";
if((i+length)>n){
return;
}
string r;
ss.assign(s, i, length);
r=ss;
reverse(r.begin(), r.end());
if(r==ss)
return;

LSP(s, i+1, length, n);
}
int main(){


string s="eabcbad";
int n = s.length();
int len=n;
while(len){
LSP(s, 0, len, n);
//cout<<len<<" "<<lsp<<endl;
if(ss!=""){
cout<<ss<<endl;
break;
}
len--;
}
}

Recurssion can be used,

Int getLongestPalindromeLength(char inputString[], int start, int end)
{
If(start == stop) return 1;
Int i = start, j = stop;
for(; i< j; i++ ){
If(inputString[i] != inputString[j])
Break;
i++; j--;
}
If(i == j) return (Start - stop + 1);
getLongestPalindromeLength(inputString[], start-1, stop);
getLongestPalindromeLength(inputString[], start, stop -1);
getLongestPalindromeLength(inputString[], start-1, stop -1);
}

Recurssion can be used,

Int getLongestPalindromeLength(char inputString[], int start, int end)
{
If(start == stop) return 1;
Int i = start, j = stop;
for(; i< j; i++ ){
If(inputString[i] != inputString[j])
Break;
i++; j--;
}
If(i == j) return (Start - stop + 1);
getLongestPalindromeLength(inputString[], start-1, stop);
getLongestPalindromeLength(inputString[], start, stop -1);
getLongestPalindromeLength(inputString[], start-1, stop -1);
}

Here is a working code in C++

#include <stdio.h>

int max_ps(char* str, int n, int max);
bool is_palindrome(char *str, int n);

int LPS(char *str, int n)
{
  return max_ps(str, n, 0);
}

int max_ps(char* str, int n, int max)
{
  int lmax = 0;
  int rmax = 0;

  if (n == 0)
  {
    return max;
  }

  if (is_palindrome(str, n) && n > max)
  {
    max = n;
  }

  lmax = max_ps( str+1, n-1, max);
  rmax = max_ps(str, n-1, max);

  if (lmax > max)
    max = lmax;

  if (rmax > max)
    max = rmax;

  return max;
}

bool is_palindrome(char *str, int n)
{
  int s = 0;
  int e = n-1;

  while(s < e)
  {
    if (*(str+ s++) != *(str + e--))
    {
      return false;
    }
  }
  return true;
}

int main()
{
  char * a = "aaacyoomimooyiabb";
  int max = 0;
  max = LPS(a, 17);

  printf ("max lps = %d\n", max);

  return 0;
}

public static int findLongestPalindromicSub(String str,int i, int j)
{
if(i>=j) return 0;

if(str.charAt(i)==str.charAt(j))
return 2 + findLongestPalindromicSub(str,i+1,j-1);

return Math.max(findLongestPalindromicSub(str,i+1,j),
findLongestPalindromicSub(str,i,j-1));
}

a

non-recursive solution if that matters..

public static string LongestPalindromeSubstring(string s)
{
    char[] charArray = s.ToCharArray();
    Array.Reverse(charArray);
    string s_r = new string(charArray);
    string palindrome = "";
    for (int i = 0; i < s.Length; i++)
    {
        string prevSubPalin = "";
        string currSubPalin = "";
        for (int j = i; j < s.Length; j++)
        {
            if (s[j] == s_r[j - i])
            {
                currSubPalin = string.Concat(currSubPalin, s[j].ToString());
            }
            else
            {
                if (prevSubPalin.Length < currSubPalin.Length)
                    prevSubPalin = currSubPalin;
                currSubPalin = "";
            }
        }

        if (prevSubPalin.Length < currSubPalin.Length)
            prevSubPalin = currSubPalin;

        if (palindrome.Length < prevSubPalin.Length)
            palindrome = prevSubPalin;
    }

    return palindrome;
}

aaasubusa> Lot of the algos above fail, as the assume the middle element is at the center of the array. For the problem it can be anywhere, for this eg, it is at Index 5.

Iterative is simple, for each Array Element, you start with it as the middle or if it +1 is the same, it and it+1 as the middle, iteratively stetch out either sides and end when you dont. Calculate the palindrome length for all elements as mid, max it.

Recurisve I probably dont see the point
For each Index as the middle
int length = Call isPalindromeWithMid with Increased Lengths starting from Index to left and right.
if Length > max update variables.

int IsPalindromeWithMid(mid, left, right)
If Left and right match
return 1 + IsPalindromeWithMod(mid, left-1, right+1)
else retunr 0;

Recursive IsPalindrome seems like a total waste of memory in terms of replacement for the iterative approach. But the question does says recursive,. I would definitely point this over to the interviewer.