CareerCup

Search term: Manacher's algorithm.

O(N).

There are 2 ways.

Either use suffix tree.
Use DFS. Remove last and first character of the strings and create 2 other strings and check for palindrome.Keep doing this for all the substring, until the palindrome is found

Use two index values to traverse over the string as "the middle values" and then use those index values to sprawl outwards from the middle to the end. You could also just get away with one index value. You just need to be aware of even/odd length palindromes.

For example,
a = {d,a,b,b,a,c}

Here you'll check [i,j] = {0,0} and [i,j] = {0,1}.

Now sprawl outwards from these two indexes. For i=0, you're limited to d since i will be less than 0 when you decrement it. For {0,0}, you'll get d and this will be your max palindrome until you get to {a,b,b,a}.

Progressing through the iterations, you'll eventually get something like [i,j] = {2,2} and {2,3}.
For {2,2}, you won't get a valid search. For {2,3}, you'll get {a,b,b,a}. Note, you'll also get {b,b} within your {2,3} search.

This should be O(N^2) time.

public class Longest_Palindrome_subsequence {//Using Dynamic Programming and filling //upper half of the diagonal table at the end the table[0][n-1] will give the result

	int lps_DP(char [] str)
	{	int n = str.length;
		int [][] table = new int[n][n] ;
		
		for(int i = 0;i<n;i++)
			table[i][i] = 1;
		
		for(int len = 2;len <=n;len++)
		{
			for(int i = 0;i <n-len+1;i++)
				{
				int j = i + len - 1;
				if(str[i]==str[j] && len ==2)
					table[i][j] = 2;
				else if(str[i]==str[j])
					table[i][j] = table[i+1][j-1]+2;
				else
					table[i][j] =Math.max(table[i][j-1],table[i+1][j]);
				}
			
			
		}
		
		
		return table[0][n-1];
	}
	
}

Dynamic programming based solution. This prints the longest palindrome.

/*
 * palindrome: output the longest contiguous palindrome in the
 * input string.
 * 
 * Usage: palindrome string
 */

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


/* bounds of a substring (both indexes inclusive) */
struct bounds {
	int start;
	int end;
};


/*
 * palindrome: Determine the longest contiguous palindrome in
 * the substring starting at index start through index end,
 * both inclusive.  Use dynamic programming (top-down with
 * memoization).
 * 
 * If s[start] == s[end], and s[start+1]..s[end-1] is a
 * palindrome, then the longest palindrome is s[start]..s[end].
 * Otherwise, the longest palindrome is the longer of the
 * longest palindrome in s[start]..s[end-1] and s[start+1]..s[end].
 * Simple cases: every single character string (start == end)
 * is a palindrome.  Empty string is a palindrome.
 * 
 * Return the longest palindrome indexes in b.
 * 
 * Maintain a cache of longest palindrome indexes in pcache.
 */
void
palindrome(const char *s, struct bounds *b, struct bounds *pcache)
{
	assert(s);
	assert(b);
	assert(pcache);
	size_t len = strlen(s);
	assert(b->start >= -1  &&  b->start <= len);
	assert(b->end >= -1  &&  b->end <= len);
	
	int start = b->start, end = b->end;
	
	/*
	 * If start > end, we have an empty string which is a palindrome.
	 * Single character strings are palindromes.
	 */
	if (start >= end)
		return;

	/* is the result already cached? */
	if (pcache[start*len + end].start != -1) {
		*b = pcache[start*len + end];
		return;
	}
	
	/* is the whole substring a palindrome? */
	if (s[start] == s[end]) {
		struct bounds inner = {start+1, end-1};
		palindrome(s, &inner, pcache);
		if (inner.start == start+1  &&  inner.end == end-1) {
			/* s[start]..s[end] is a palindrome */
			pcache[start*len + end] = *b;
			return;
		}
	}
	
	struct bounds inner1 = {start+1, end};
	palindrome(s, &inner1, pcache);
	struct bounds inner2 = {start, end-1};
	palindrome(s, &inner2, pcache);
	int len1 = inner1.end - inner1.start;
	int len2 = inner2.end - inner2.start;
	if (len1 > len2)
		pcache[start*len + end] = *b = inner1;
	else
		pcache[start*len + end] = *b = inner2;
}


/*
 * longest_palindrome: Allocate the cache and then call palindrome to
 * get the longest palindrome.  Finally, free the cache.
 */
void
longest_palindrome(const char *s, struct bounds *b)
{
	assert(s);
	assert(b);
	size_t len = strlen(s);
	assert(b->start == 0);
	assert(b->end == len-1);
	
	struct bounds *pcache = malloc(len * len * sizeof(struct bounds));
	assert(pcache);
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++)
			pcache[i*len + j].start = pcache[i*len + j].end = -1;
		
	palindrome(s, b, pcache);
	
	free(pcache);
}


int
main(int argc, const char *argv[])
{
	if (argc != 2) {
		fprintf(stderr, "Usage: palindrome string\n");
		return 1;
	}
	
	const char *s = argv[1];
	struct bounds b = {0, strlen(s)-1};
	longest_palindrome(s, &b);
	
	printf("Longest palindrome of %s is ", s);
	const int end = b.end;
	for (int i = b.start; i <= end; i++)
		printf("%c", s[i]);
	printf("\n");
	
	return 0;
}

private static boolean isSubstringPalyndrome(char[] charSeq, int start, int end) {
while(start<end) {
if(charSeq[start] != charSeq[end]) return false;

start++;
end--;
}
return true;
}

private static int findLengthOfMaxLengthPalyndrome(String s) {

char[] stringAsCharSeq = s.toCharArray();

int maxLength = 1;

for(int i = 0; i < stringAsCharSeq.length; i++) {
for(int j = i+maxLength ; j < stringAsCharSeq.length; j++) {
if( isSubstringPalyndrome(stringAsCharSeq, i, j) ) maxLength = j - i + 1;
}
}

return maxLength;

}