## Microsoft Amazon Interview Question

Software Engineer / Developers```
public class LongestPalindrom {
public static void main(String args[]) {
String str = " hello . you uoy era woh..";
char[] a = str.toCharArray();
int low = Integer.MAX_VALUE;
int upper = Integer.MIN_VALUE;
for (int i = 0; i < str.length(); i++) {
int start = i;
int end = i;
while (start >= 0 && end < str.length()) {
if (a[start] == a[end]) {
if (end - start > upper - low) {
upper = end;
low = start;
}
end++;
start--;
} else {
break;
}
}
}
for (int i = 0; i < str.length(); i++) {
int start = i;
int end = i + 1;
while (start >= 0 && end < str.length()) {
if (a[start] == a[end]) {
if (end - start > upper - low) {
upper = end;
low = start;
}
end++;
start--;
} else {
break;
}
}
}
for (int i = low; i <= upper; i++) {
System.out.print(a[i]);
}
}
}
```

```
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Kalpana Shah
*/
public class Test1 {
public static void main(String args[]) {
String pali = "ihelloolleh";
int paliLen = pali.length();
int matchLen = 0;
int startIndex = 0;
int finalSize = 0;
int finalIndex = 0;
for( int i = 0 ; i < paliLen ; i++ ) {
for( int j = (paliLen - 1) ; j >= i ; j-- ) {
if( pali.charAt(i) == pali.charAt(j) && ( i != j ) ) {
System.out.println( "Character at : " + i + " matches character at : " + j + " and it is : " + pali.charAt(i) );
matchLen = 0;
int k = 0;
int l = 0;
for( k = i , l = j ; ( k < paliLen ) && ( l >= 0 ) ; k++ , l-- ) {
if( pali.charAt(k) != pali.charAt(l) ) {
break;
}
else {
matchLen++;
startIndex = i;
}
}
if( matchLen > finalSize ) {
finalSize = matchLen;
finalIndex = startIndex;
}
}
}
}
System.out.println("Exiting Main Now");
System.out.println("The Maximum Size is : " + finalSize );
System.out.println("The Final is : " + finalIndex );
for( int z = 0 ; z < finalSize ; z++ ) {
System.out.print(pali.charAt(finalIndex+z));
}
}
}
```

Actually, the most efficient algorithm is O(n) and is based on dynamic programming.

Let str be the string of length n.

Let us define:

len[i] = length of the longest palindrome in substring having characters str[0],str[1],...,str[i].

beginIndex[i] = beginning index of the longest palindrome in substring having characters str[0],str[1],...,str[i].

len[0] = 1;

beginIndex[0] = 0;

Now, try to find out len[i] in terms of len[i-1] and beginIndex[i] in terms of beginIndex[i-1] - during this we should leglect the special case when all characters in palindromes are same. We should find maximum length palindrome of this type.

We should deal with the special case where all characters in palindromes are same separately and find the maximum length palindrome of such type.

Out of above two, we should pick the longer palindrome. More than enough to solve it.

In any case, full code is below:

public static String longestPalindrome(String str)

{

String result = "";

int[] bIndex = new int[str.length()];

int[] len = new int[str.length()];

int i = 0, j = 0, index = 0;

bIndex[0] = 0;

len[0] = 1;

if(str.charAt(0) == str.charAt(1))

{

bIndex[1] = 0;

len[1] = 2;

}

else

{

bIndex[1] = 1;

len[1] = 1;

}

int maxLen = 0, bIndexMax = -1;

char c;

for(i = 0; i < str.length(); i = j)

{

c = str.charAt(i);

for(j = i+1; j < str.length() && str.charAt(j) == c; j++);

if(maxLen < j-i)

{

maxLen = j-i;

bIndexMax = i;

}

}

for(i = 2; i < bIndex.length; i++)

{

index = bIndex[i-1];

if( index == i-1)

{

if(str.charAt(i-2) == str.charAt(i))

{ // check for odd length palindrome

bIndex[i] = i-2;

len[i] = 3;

}

else if(str.charAt(i-1) == str.charAt(i))

{

bIndex[i] = i-1;

len[i] = 2;

}

else

{

bIndex[i] = i;

len[i] = 1;

}

}

else

{

if(index-1 < 0)

{

bIndex[i] = i;

len[i] = 1;

}

else if(str.charAt(index-1) == str.charAt(i))

{

bIndex[i] = index-1;

len[i] = len[i-1] + 2;

}

else

bIndex[i] = i;

}

}

for(i = 0; i < len.length; i++)

{

if(maxLen < len[i])

{

maxLen = len[i];

bIndexMax = bIndex[i];

}

}

return str.substring(bIndexMax,bIndexMax + maxLen);

}

This self-contained C program will print out all of the palindrome lengths for all possible centers, and it will do it in O(n) time. It is a port of the algorithm in Haskell authored by Johan Jeuring here: johanjeuring.blogspot.com/2007/08/finding-palindromes.html

```
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// Simple linked list functions
typedef struct Node Node;
struct Node {
int len;
Node* next;
};
Node* insertNode(Node* head, Node* node) {
node->next = head->next;
head->next = node;
return node;
}
Node* createNode(int len) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->len = len;
return newNode;
}
Node* insertNum(Node* head, int len) {
return insertNode(head, createNode(len));
}
void printReverse(Node* node) {
if (node != NULL) {
printReverse(node->next);
printf("%d ", node->len);
}
}
void printReverseList(Node* head) {
printReverse(head->next);
printf("\n");
}
void cleanList(Node* head) {
Node* curr = head;
while (curr != NULL) {
Node* next = curr->next;
free(curr);
curr = next;
}
}
int main(int argc, char* argv[]) {
if (argc < 2) {
printf("USAGE: ./pal string\n");
return 0;
}
char* a = argv[1];
int n = 0;
int len = strlen(a);
int currTail = 0; // length of the longest tail palindrome
Node* centers = createNode(0);
centers->next = NULL;
while (n < len) {
if (n - currTail != 0 && a[n - currTail - 1] == a[n]) {
n++;
currTail += 2;
continue;
}
Node* center = centers->next;
insertNum(centers, currTail);
int centerDist = currTail;
while (centerDist != 0 && center != NULL && centerDist - 1 != center->len) {
centerDist--;
insertNum(centers, center->len > centerDist ? centerDist : center->len);
center = center->next;
}
if (centerDist == 0) {
n++;
currTail = 1;
} else {
currTail = center->len;
}
}
Node* center = centers->next;
insertNum(centers, currTail);
while (currTail != 0) {
currTail--;
insertNum(centers, center->len > currTail ? currTail : center->len);
center = center->next;
}
printReverseList(centers);
cleanList(centers);
return 0;
}
```

This counter example isn't correct. LCS of the string and reverse is abccba. It's a valid palindromic substring of the input.

find palindrome in string A

reverse A as A', so it's equivallent to find longest common substring between A and A'?

if so, we can use prefix array method to do this as the "pearls" book suggested?

This is a problem of finding the LCS(longest common subsequence ) between the string and the its reverse.

1. Original string is A

2. Reverse string is B

3. Find common strings are C, D, E ....

4. Find palindromic strings in step 3, suppose C, D.

5. Find the max length of strings in step 4. Return.

it does work, but you have to find common string in this way:

public static String FindCommonString(String str1, String str2)

{

if(str1.length()!=str2.length()) return null;

StringBuilder sb=new StringBuilder();

for(int i=0;i<str1.length();i++)

{

if(str1.contains(str2.substring(i)))

{

sb.append(str2.substring(i));

break;

}

}

return sb.toString();

}

Needs some change of the code above:

public static String FindCommonString(String str1, String str2)

{

if(str1.length()!=str2.length()) return null;

StringBuilder sb=new StringBuilder();

int maxLength=0;

for(int i=0;i<str1.length();i++)

{

for(int j=0;j<str2.length();j++)

{

int compLength=str2.length()-j-i;

if(compLength<=1)break;

if(str1.contains(str2.substring(i,str2.length()-j)))

{

//System.out.println(str2.substring(i,str2.length()-j));

if(compLength>maxLength)

{

maxLength=compLength;

sb.append(str2.substring(i,str2.length()-j));

System.out.println(sb.toString());

}

}

}

}

return sb.toString();

}

Here's a solution in C++ (may not be the most effective, though). Basically it checks if the given string "s" is a palindrome. If it is, then that's the longest we can find.

If not a palindrome, look in s.substr(0, len - 1) and in s.substr(1, len - 1) and return the longest result.

```
#include <cassert>
#include <iostream>
#include <string>
#include <utility>
using namespace std;
static size_t distance(const pair<size_t, size_t>& p)
{
assert(p.first <= p.second);
return p.second - p.first;
}
//count how many times find_longest_palindrome is invoked
static size_t count = 0;
static pair<size_t, size_t> find_longest_palindrome(const char* s, size_t len)
{
++count;
pair<size_t, size_t> result;
#if 0
//move outwards beginning from the middle
size_t i = len / 2, j = len / 2;
if (len && len % 2 == 0)
{
assert(i > 0);
--i;
}
for (; j < len; ++j, --i)
{
assert(i < len);
if (s[i] != s[j])
{
break;
}
result.first = i;
result.second = j;
}
if (len > distance(result) + 1)
{
//inspect right hand-side substring
pair<size_t, size_t> result1 = find_longest_palindrome(s, len - 1);
if (distance(result) < distance(result1))
{
result = result1;
}
//inspect right hand-side substring
pair<size_t, size_t> result2 = find_longest_palindrome(s + 1, len - 1);
if (distance(result) < distance(result2))
{
result = result2;
++result.first;
++result.second;
}
}
#else
//work inwards from the extremities of the string
size_t i = 0, j = len ? len - 1 : 0;
result.first = 0;
result.second = j;
for (; i < j; ++i, --j)
{
if (s[i] != s[j])
{
result.second = 0;
break;
}
}
if (!result.second && len > 1)
{
//inspect right hand-side substring
result = find_longest_palindrome(s, len - 1);
//if the length found == len - 1 there's no point in inspecting
//the right hand substring
if (distance(result) < len - 1)
{
//inspect right hand-side substring
pair<size_t, size_t> result2 = find_longest_palindrome(s + 1, len - 1);
if (distance(result) < distance(result2))
{
result.first = result2.first + 1;
result.second = result2.second + 1;
}
}
}
#endif
return result;
}
string find_longest_palindrome(const string& s)
{
count = 0;
pair<size_t, size_t> r = find_longest_palindrome(s.c_str(), s.length());
#if _DEBUG
cout << '[' << r.first << ", " << r.second << ']' << endl;
cout << "string length=" << s.length() << ", number of steps=" << count << endl;
#endif
return distance(r) ? s.substr(r.first, distance(r) + 1) : string();
}
void main()
{
cout << find_longest_palindrome("abcd") << endl;
cout << find_longest_palindrome("xxbaaba") << endl;
cout << find_longest_palindrome("xxbaabaa") << endl;
cout << find_longest_palindrome("xxba") << endl;
cout << find_longest_palindrome("yyyba") << endl;
cout << find_longest_palindrome("xxbaabaawowaabx") << endl;
}
```

1) Naive algorithm finds he solution for the problem in O(n3) time.

Select two ends to define a substring and check in linear time whether it is a palindrome.

2)Enhancement can be done to the naive algorithm to make it work in O(n2) time and O(n) space.

Consider two strings S and S(reverse).

for each character in first string:

for each subpattern in first string match the pattern in second string by KMP algorithm to find longest common string in both in linear time O(n+n) and O(n) space(this will be the palindrome).

overall runtime O(n2) and O(n) space.

3)The optimized version of the algorithm runs in O(n) time with suffix trees.

first identify the non repeating characters in the string it cannot be the part of a palindrome unless <br>

s[i-1]=s[i+1](otherwise we may get palindrome of size as long as i traverses..].so we need to search in s[0...i-1] and s[i+1...n-1].. i hope this may help reducing the problem into parts..

first identify the non repeating characters in the string it cannot be the part of a palindrome unless <br>

s[i-1]=s[i+1](otherwise we may get palindrome of size as long as i traverses..].so we need to search in s[0...i-1] and s[i+1...n-1].. i hope this may help reducing the problem into parts..

Input String is s1, Reverse the string to s2.

Use Dynamic Programming to find the longest common substring. That gives u the result!

Okay genius, how about the string "abcdefcba"? The reverse is "abcfedcba" and the longest common substring is either "abc" or "cba". Are those palindromes? Think about that.

Instead of DP, build a suffix tree and starting from longest common substring, find a palindrome.

I kind of disagree from sameerud, because take an example of a string abcaba,,,

so as i understand his algo. won't be able to find the pallindrome aba,,

So, i there is one another algo

char *lar_pal = NULL;

char *str = /*some string*/

for(int i=0;i<strlen(str);i++){ //iterate over all of the string

for(int j=i+1;j<strlen(str);j++){

}

}

Sorry for previous reply,, pressed enter by mistake

I kind of disagree from sameerud, because take an example of a string abcaba,,,

so as i understand his algo. won't be able to find the pallindrome aba,,

So, i there is one another algo. (I should write sudo code)

1) Start from the first element i in the string and compare it will all other element j in the

string //for(j=i+1;j<strlen(somestr);j++)

a) if string[i] == string[j]

if(pallindrome(somestr,i,j)){

//the substring is from i - j index

}

pallindrome(char *someStr, int i, int j)

1) if someStr[i+1] == someStr[j-1]

if(i==j || i+1 == j) //aba,,,,abba

return true

aii) else

i+=1;j-=1;

pallindrome(someStr,i,j)

else

return false

This is a Longest Common Substring Problem,we basically construct the generalized suffix tree for the give string and its reverse.From the constructed tree it would be possible to find the longest Palindrome by traversing the tree.The construction of the tree would take O(n).

if the string is '123451254321' and we find the longest common substring with its reverse, the result would be '12345'. But this doesn't seem right.

@Anonymous 123451254321 when reversed would give 123452154321 ,so how do you say that the longest common palindrome would be 12345,unless you have a palindrome pattern in the main str ,its revers will not contain any palindrome.

For instance 'This is the end' here the longest palindrome is 'e e',upon reversing this string we get 'dne eht si siht ' again the longest palindrome for this string is e e.So the longest common palindrome ends up being 'e e'.In your example I dont see any such pattern.Correct me if i have mistaken your explanation/question.

Ok first,You need to know what a palindrome is "MADAM" when reversed still remains MADAM,likewise RACECAR when reversed gives RACECAR,Similarly EYE when reversed gives EYE.So A string is a palindrome only when its reverse also yields the same string.

@Vijgan "This is the end"reverse it what do you get

Original:"This is the end"

Reversed:"dne eht si siht" ,so the longest palindrome cannot be "si si",only if it was "si is" it is a palindrome.Hence here the longest palindrome would be "e e".I hope this is clear.

My views:

1. Start with the middle element in the String (len/2).

2. Have two pointers (i and j): i goes back till 0, j goes forward till n.

3. whenever this fails : you have your longest palindrome.

This can be done other way too:

1. Have two pointers i and j at the beginning and at the end.

Like wise. Any takers?

Ur idea is good one...i successfully implemented it (of course with modifications but basic idea is as u said )... tested with tools and 100% working...now moving to suffix tree implementation....lets see how it goes...anyways thnx raj..

How does this work when you have helloaba? in this case you won't find aba, since i and j will never equal?

Yes, Flag is right.

We can change his idea a little bit to make it work:

1) i goes from 0 to 2n

2) r is a radius around i in which we look for a palindrome, and we keep the max

For helloaba we would have

i = 0, subPalindrome(h)??? max = 1

i = 1, subPalindrome(he)??? max = 1

i = 2, subPalindrome(hel)??? max = 1

i = 3, subPalindrome(el)??? max = 1

i = 4, subPalindrome(ell)??? max = 1

i = 5, subPalindrome(ll)??? max = 2 radius increases

i = 6, subPalindrome(ello)??? max = 2

...

i = ..., subPalindrome(ab)??? max = 2

i+1, subPalindrome(aba)??? yes ===> max = 3. radio would increase, but we got to the end of the word

If we had done i from 0 to n, it wouldn't work for abba, for instance. Like this we cover palindromes which are not centered in a specific letter.

Source : leetcode.com

@particularraj: your algorithm works by the assumption that the palindrome starts in the middle of the string. It doesn't consider palindromes that at other places in the string. For example, consider the string

ABMOCECXYYZ

Here according to your algorithm, you will start at 'E' moving i backward and j forward. When i reaches 'O' and j reaches 'X', the algorithm stops and concludes that 'CEC' is the longest palindrome. But 'XYYZ' is the longest palindrome in the above mentioned string.

Is there any O(n) solution other than suffix tree. I dont think the interviewer would ask you to construct a suffix tree during the interview.

Suffix tree will give a very good solution, but it is difficult to come up in a interview. I would go with a dynamic programming approach,

Suppose we have the given string as,

InputString = "abaccabadefg"

Here there are 4 palindrome strings,

aba - length 3

cc - length 2

aba - length 3

abaccaba - length 8

Now the output should be abaccaba

In order to find that, reverse the input string,

ReverseString = "gfedabaccaba"

Now create a 2 dimensional matrix of NxN and follow a dynamic program approach to get the length on the longest palindrome and display it. Heart of the solution is,

A[i,j] = Max (a[i-1, j], a[i,j-1] if InputString[i] != ReverseString[j]

= a[i-1,j-1] + 1, if InputString[i] == ReverseString[j]

How about having two pointers, one at the start and one at the end of the string. For each character in the string, you will traverse backwards from the tail and try to find the largest possible palindrome matching with the start of the strong, if any. You keep doing for every character, this until you find one, any palindrome. Each time you do this loop for a character from the head, your largest palindrom will be s-n, where s is the original string length, and n is the number of iterations you've done this. When you do find a palindrome, any palindrome, you will know that if the largest palindrome, it will be at between size (curr palindrom size) and (s-n). Armed with this knowledge, you can then write a function that is optimized to only process the remainder of the array for strings that meet the stringlength described above.

And of course, this could be done elegantly using recursion, and fine tuning it with the logic similar to the above once you have confirmed at least one palindrome. This of course is going to be a resource hog but the code will be easier to read and manage.

:)

1. Find the reverse string

2. Find longest common substring

Will this work? I think dynamic programming approach that you mentioned is same as this.

Even I feel the same.

@Tejas

Even though you said to use dynamic programming, your solution's major idea was to reverse the source string and find the common substring.

Now take a look at this string "abcdecba". If you reverse the string, you would get "abc" and "cba" as palindromes, which is incorrect.

I hope only suffix trees would give an O(n) solution. Any other solution that we would give in an interview, would definitely be O(n^2) or higher(because a string with length n has n^2 substrings). Anybody disagrees with this statement guys??

Tell me if I'm wrong, it will take O(n^3), right?

Loop structure could be something like following

i = 0 -> n

j = i-> n

k = j -> n

Take a string

1. Reverse the string

2. XOR with the Original String

3. Find the longest sequence of 0s in the XORed result which will be the corresponding answer

reverse of RACECAR is RACECAR only .... so xoring dem wud giv 0000000 .... which is the longest palindrome ... i think vishal's solution will work for all cases ...

reverse of RACECAR is RACECAR only .... so xoring dem wud giv 0000000 .... which is the longest palindrome ... i think vishal's solution will work for all cases ...

that is an awesome approach.. guess it will work for all cases...

small patch: if XORing is tough for charecters while coding... we can just subtract both the strings charecter by charecter... and then count the max no of consecutive zeros....

You need to shifting windows to make this work:

```
def palindrome(string):
'''
Returns the longest palindrome in string.
'''
reverse = string[::-1]
winner = ''
if string == reverse:
return string
sources = [(string, reverse), (reverse, string)]
for source_a, source_b in sources:
for window in range(1, len(source_a) - 1):
string_a = source_a[:-window]
string_b = source_b[window:]
results = compare(string_a, string_b)
for result in results:
if len(result) > len(winner):
winner = result
return winner
def compare(string_a, string_b):
'''
Compares two strings of equal length and finds any common strings between
the two.
'''
result = []
# True if a commonality is being extracted. This flag lets us know when to
# insert a new value into result.
found = False
for index in range(len(string_a)):
if string_a[index] == string_b[index]:
if not found:
result.append('')
found = True
result[-1] += string_a[index]
else:
found = False
return result
from sys import argv
print palindrome(argv[1])
```

start with the first character. try to lookup the same character from the bak. on finding the same character from the back check if the substring is palindrome or not. keep on finding the same character until u reach the index of the first character.

keep on doing the same for all the characters. ....O(n^2)

finding the longest substring of the string and it's reverse won't work. Consider

abcdefgHELLOWORLDgfedcba The longest palindrome is actually LL, that method would return abcdefggfedcba

Keep a current pointer on the second element a(1). place two other pointers at current-1 and current+1. check if curr-1 and curr+1 are equal. then move current pointer ahead. again set curr-1 and curr1 and check for:

If curr is at ith position:

while(i>0)

{

if (curr-1 == curr+1)

{

(curr+1)++;

(curr-1)--;

i--;

}

else break;

}

keep tack of the largest one by storing the value of current for which the length of palindrome was max. also keep track of it's length for each i. Then u can print the longest palindrome.

No, It doesnot... because i assumed that palindrome will be of odd length...

For this case... place a current ptr and move the curr+ ptr till it goes to the value which is not equal to the current ptr. and then follow the steps above.

I think we cannot solve this question in less than O(n^3) complexity........as ideally there are n*n different string that can be created using a string of length n......For example there are 1 string of length n that can be formed from given string and there are 2 string of length n-1 that can be formed using a string of lenght n-1 and there are n string of length 1.

So if you sum it all, there are 1+2+ ........+ n-1 + n strings = O(n*n)........

We know how to check for one string in O(n) time, so I think we can just repeat the loop by checking string of length n to 1 and stop whenever we find any palindrome.....

Seriously, I don't think we can solve this question in less than this time, because we have to check for string of each length and in worst case there might not be any palindrome in string and so we might end up with generating palindrome on length 1 i.e . character itself, if you consider that to be a palindrome.....

Please share your thoughts, I would be happy to hear from anyone....who can help me in improve on this solution...........

```
maxindex = 1;
maxlen = 1;
for(index = 1 to str.length) {
for(cur = 1 to min(index, abs(str.length - index))) {
if(str[index + cur] == str[index - cur]) {
if(cur < maxlen) continue;
maxlen = cur;
maxindex = index;
}
}
}
```

May fail for the boundary conditions. But this the logic which i can think of for O(n2) complexity.

We need two such code blocks one for even length and one for the odd length.

Hence the time complexity is O(n2). O(1) space complexity

I am not sure about suffix tree, as I have not read those yet, but I don't think we can solve this question iteratively in less than O(n^3) and I don't think dynamic programming will work too as we cannot use the result that I got in previous iteration because if I have two strings that are palindrome then I cannot say that if I merge both string then those will be palindrome also...

Here is my solution using O(n^3) complexity.

There are n*n different string that can be created using a string of length n......For example there are 1 string of length n that can be formed from given string and there are 2 string of length n-1 that can be formed using a string of lenght n-1 and there are n string of length 1.

So if you sum it all, there are 1+2+ ........+ n-1 + n strings = O(n*n)........

We know how to check for one string in O(n) time, so I think we can just repeat the loop by checking string of length n to 1 and stop whenever we find any palindrome.....

Seriously, I don't think we can solve this question in less than this time, because we have to check for string of each length and in worst case there might not be any palindrome in string and so we might end up with generating palindrome on length 1 i.e . character itself, if you consider that to be a palindrome.....

Please share your thoughts, I would be happy to hear from anyone....who can help me in improve on this solution...........

A working solution. O(n*n*n) complexity but good for an interview.

```
bool ispalindrome (const char * start, const char * end)
{
while (start < end)
{
if (*start != *end)
{
return false;
}
start++;
end--;
}
return true;
}
char * longestPalindrome(const char * str_p)
{
int len = strlen (str_p);
const char * startOfPal = 0; // start of palindrome.
const char * endOfPal = 0; // end of palindrome.
int maxLenOfPal = 0; // len of palindrome.
for (int i = 0; i < len; i++)
{
for (int j = len-1; j > i; j--)
{
const char * start = str_p + i;
const char * end = str_p + j;
if (ispalindrome(start, end))
{
if ((end - start + 1) > maxLenOfPal)
{
startOfPal = start;
endOfPal = end;
maxLenOfPal = end - start + 1;
}
}
}
}
```

Not sure what happened to the white space.

Here is a quick test I used.

```
const char * str = "testanaradaring";
char * x = longestPalindrome(str);
if (x)
{
cout << x << endl;
}
else
{
cout << "No palindrome found." << endl;
}
```

How about this way:

1. define stringbulder variable called sb and an int called numberOfChars and max

2. for each character in the string

3. add the character to sb, and set numberOfChars to 1.

4. for each remaining character in the string

5. append the character to sb and increment numberOfChars by 1.

6. if the character is the same as the character read in step 2, then what we have in sb is a potential palindrom so, call a helper funtion called IsPalindrome with the value in sb as an argument.

7. If step 6 returns true, then add the content of sb to a dictionary with sb as a key and numberOfChars as a value---you can have duplicate checks

8. inner loop ends here

9. if numberOfChars > max then reset max to numberOfChars and clear sb

9. loop to the first loop.

10. Now, all possible palindrome strings are in your dictionary. Return a key with value equal to max.

Note that:

The algorithm generates all possible palindroms but, i think there might be a better way of doing it.

Precisely. One moethod is what anonymous quoted. reverse and find the longest common substring. O(n2) method.

Second could be for every possible position in the string find the palindrome and keep track of the max found so far. One also has to take care of odd length and even length strings.

AGain O(n2) method.

Example:

================

Str1=abcbabcmoms

Str2=abcba

ALGO:

================

1.a take A[i]==A[j] , decrement J-- till i

if A[i]==A[j]

take paldromeindex=i

and increment i and decrement j till i=j

RANGE[k]=J-I

1.b sort range and return the longest one

CODE:

================

private string LongestPalindrom(Str S1,int size)

{

int maxrange =0;

For(int i=0;i<size ; i++)

{

char ch1=s1[i];

FOR(INT J=SIZE; J>0;J--)

{

char ch2=s1[j];

IF(CH1==CH2 && i!=j)

{

int range= j-i;

i++;

ch1=s1[i];

}

}

IF(MAXRANGE<RANGE)

{

int maxrange =range;

int maxindex=i

}

}

FOR(k=maxindex;k<i+maxrange;K++) \\Printing the Longest Palindrome

{

Console.writeline(Str[k]);

}

}

TEST HARNESS:

================

using system;

namespace problem

{

class Solution

{

static void Main(string[] args)

{

String Pal1 ="abcbabcmoms"

String Result;

Result= Longestpalindrom(Pal1,11);

}}}

ORDER:

================

O(N^2)

Tarun,

Nice try but you need more temp variables to save indexes and values. Try this string and you will find a bunch of bugs in ur code.

"BBABTENETTENEB".

This is is the code i came up with, can you guys please review it:

void longestPalindrome(char* str, int size, int* begin, int* range){

*begin = 0;

*range = 0;

int i, j, pali, tempRange = 0;

for(i = 0; i < size; i++){

*begin = pali = i;

for(j = size - 1; j >= pali; j--){

tempRange = j - *begin;

if(str[pali] == str[j]){

pali++;

}else{

tempRange = 0;

if(pali != *begin){

break;

}

}

}

if(*range < tempRange){

*range = tempRange;

}

}

}

```
void longestPalindrome(char *str, int n)
{
int i=0, j=0, start = 0, end = 0, range = 0, maxstart = 0,maxend = 0;
while(i < n && j < n)
{
start = i; end = j;
while((str[start] == str[end]) && (start >=0) && (end <= n))
{
if((maxEnd - maxStart) < (end-start))
{
maxEnd = end;
maxStart = start;
}
end++;
start--;
}
start++;
end++;
}
for(int i = maxStart; i <= maxEnd; i++)
printf("%c", str[i]);
}
```

This is indeed a Dynamic Programming problem as Gopal Krishna has indicated but I can't think of a a solution that can solve this in less than O(n2).

My O(n2) solution was to take the string and its reverse (i.e. output of strrev(string)) and do a longest sub-string match using dynamic programing. The largest sub-string match is the longest palindrome in the given string.

<pre lang="c#" line="1" title="CodeMonkey63324" class="run-this">using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;

class Program

{

static void Main(string[] args)

{

Program p = new Program();

Console.WriteLine(p.LargestPalindrome("abbac");

}

public String LargestPalindrome(String str)

{

int[] ar = new int[str.Length];

for (int i = 0; i < str.Length; i++)

{

int start = i;

for (int j = str.Length - 1; j >= i; j--)

{

int end = j;

int cnt = 0;

while (start <= end)

{

if (str[start] == str[end])

{

if (start != end)

cnt += 2;

else

cnt++;

start++; end--;

}

else

{

cnt = 0;

break;

}

}

if (ar[i] < cnt)

ar[i] = cnt;

}

}

int max = 0;

for (int i = 1; i < ar.Length; i++)

{

if (ar[i] > ar[max])

max = i;

}

return str.Substring(max, ar[max]);

}

}</pre><pre title="CodeMonkey63324" input="yes">1

2

10

42

11

</pre>

int _tmain(int argc, _TCHAR* argv[])

{

char p[500],*temp;

int i,j,str_len,k;

printf("\n Enter the string ");

gets(p);

if (palendrome(p) == 0) {

printf("\n String is a palendrome");

return 1;

}

else

printf("\n Not a palendrome");

str_len = strlen(p);

int largest_palindrome = 0;

char q[100];

for(i=0;i<str_len;i++)

{

temp = p+i;

for(j=2;j<=str_len-i;j++)

{

if(palendrome_substring(temp,j) == 0)

{

if (j > largest_palindrome){

largest_palindrome = j;

memcpy(q,temp,j);

q[j] = '\0';

}

}

}

}

printf("\n largest palendrome %s",q);

return 0;

}

int palendrome(char *p)

{

int str_len = 0,i;

if (!p ) return -1;

str_len = strlen(p);

if(str_len < 2)return 1;

for(i=0;i<(str_len/2);i++)

{

if (p[i] != p[str_len - i - 1])

return 1;

}

return 0;

}

int palendrome_substring(char *p, int size)

{

int str_len = 0,i;

if(!p || !size) return -1;

str_len = size;

for(i=0;i<(str_len/2);i++) {

if (p[i] != p[str_len - i - 1])

return 1;

}

return 0;

}

```
N^2 solution - Dynamic Programming. Should be good for interview.
isPalindrome[i,j] = isPalindrome[i+1, j-1], if str[i] == str[j]
= false, if str[i]!= str[j]
= true, if i == j //single character
After the matrix is filled, traverse diagonally to find the longest palindrome
```

```
#include<stdio.h>
#include<malloc.h>
#include<string.h>
int getLength(char* input)
{
int len = 0;
while(*input)
{
len++;
input++;
}
return len;
}
//O(n*n) DP solution
void longestPalindrome(char* input)
{
if(!input) return;
int length = getLength(input);
//Allocate a length*length table of boolean values
bool** DP = (bool**)malloc(length*sizeof(bool*));
for(int i = 0; i < length; i++)
DP[i] = (bool*)malloc(length*sizeof(bool));
int row = 0;
int col = 0;
int currCol = 0;
//This loop traverse just the upper half of the matrix and populates it
while(col < length)
{
while(row < length && col < length)
{
if(row == col) DP[row][col] = true;
else if(input[row] == input[col])
{
//If they are adjacent chars and equal, then it is a palindrome
if(col == row+1) DP[row][col] = true;
//Check if the contained string is a palindrome
else DP[row][col] = DP[row+1][col-1];
}
else DP[row][col] = false;
row++;col++;
}
row = 0;
currCol++;
col = currCol;
}
//Traverse the matrix diagonally to find the longest palindrome.
row = 0, col = 0, currCol = 0;
int maxi = 0;
int maxy = 0;
while(col < length)
{
while(row < length && col < length)
{
if(DP[row][col] == true)
{
maxi = row;
maxy = col;
}
row++; col++;
}
row = 0;
currCol++;
col = currCol;
}
//maxi and maxy hold the beginning and ending of the longest palindrome
printf("Longest Palindrome is : ");
while(maxi <= maxy)
{
printf("%c", input[maxi]);
maxi++;
}
printf("\n");
}
int main()
{
char input[] = "mississippi";
longestPalindrome(input);
}
```

```
char * longPlaindrome (char *str)
{
char * pointpal;
while(*str)
{int i=1;
if(*str==*(str+i)||*(str-i)==*(str+i))
{
if (*(str-i)==*(str+i))
pointpal=str-i;
else
pointpal=str;
i++;
while(*(str-(i-1))==*(str+i)||(*str-i)==*(str+i))
{
pointpal--;
i++;
}
}
str++;
}
return pointpal;
}
int main()
{
char * str1="ABMOCECXYYXOPQR";
char * longestpal=longPlaindrome(str1);
char * point=longestpal;
int loop=1;
while(loop)
{
cout<<*longestpal;
longestpal++;
if (point==longestpal)
{
loop=0;
}
if(*point==*longestpal)
point=longestpal+1;
}
cout<<endl;
return 1;
}
```

```
small change in previous program:
char * fndlong (char *str)
{
char * pointpal, *longestpal;
int length, longest=0;
while(*str)
{int i=1;
if(*str==*(str+i)||*(str-i)==*(str+i))
{
if (*(str-i)==*(str+i))
pointpal=str-i;
else
pointpal=str;
i++;
length=0;
while(*(str-(i-1))==*(str+i)||(*str-i)==*(str+i))
{
pointpal--;
i++;
length=+ 2;
}
}
if(longest==0 || length>longest)
{
longest=length;
longestpal=pointpal;
}
str++;
}
return longestpal;
}
int main()
{
char * str1="ABMABCDDCBAOCECXYYXOPQR";
char * longestpal= fndlong(str1);
char * point=longestpal;
int loop=1;
while(loop)
{
cout<<*longestpal;
longestpal++;
if (point==longestpal)
{
loop=0;
}
if(*point==*longestpal)
point=longestpal+1;
}
cout<<endl;
return 1;
}
```

program to find longest palindrome:

int main()

{

int i,j,count=0,check=0,loc=0,pos=0;

string str;

cout<<"enter string"<<endl;

cin>>str;

for(i=1;i<str.length();i++)

{

for(j=i;j<str.length();j++)

{

if(j-1<0 || j+1>=str.length())

break;

if(str[j-1]==str[j+1])

{

count++;

loc=j;

}

else

break;

}

if (count>check)

{

check=count;

pos=loc;

}

}

for(int k=(pos-check);k<=(pos+check);k++)

cout<<str[k];

}

```
The idea is to go left and right from each element until left will be the beginning, or right will be the end.
The initial length of each possible palindrome is 1.
We need to distinguish 2 cases:
1). "Odd" case, like "abcdcba"
2). "Even" case, like "dcbaabcd"
In "even" case, we need to shift our "right" pointer to one position right and to increasr the current length.
During each next move, we increase our current palindrome length on 2, if the left and the right characters are the same.
When palindome stops (we reach the array borders, or our left and right characters are not the same any more),
we compare our current palindrome length with the previous maximal length.
void FindLongestPalindrome(char Arr[])
{
char* pCurr; // moving through our string
char* pBegin; // the beginning of the string
char* pEnd; // the end of the string
char* pLeft; // to go left from the current character
char*pRight; // to go right from the current character
int iMaxIndex=0;
int iCurIndex=0;
int iMaxLength=1;
int iLength;
pCurr=pBegin=&Arr[0];
pEnd=pBegin;
while(1)
{
pEnd++;
if(*pEnd=='\0') break;
}
// now pEnd points to the end of our array
while(1) // go through the array
{
iLength=1;
//Odd case:
pLeft=pRight=pCurr;
//even case:
if((*pLeft)==(*pRight+1))
{
pRight++;
iLength++;
if(pRight>pEnd) break;
}
while(1)
{
if((*pRight) != (*pLeft)) break;
pLeft--;
pRight++;
if((pLeft<pBegin) || (pRight>pEnd)) break;
iLength = iLength+2; // because we add characters from the left and from the right
}
if(iLength > iMaxLength)
{
iMaxLength = iLength;
iMaxIndex = iCurIndex;
}
pCurr++;
if(pCurr>pEnd) break;
iCurIndex++;
}
// Now we have iMaxIndex as the beginning of longest palindrome, and iMaxLength as it's length
for(int i=iMaxIndex; i<=iMaxIndex+iMaxLength; i++)
printf("%c", Arr[i]);
printf("\n");
}
```

Reverse the string and compare using a shifting window.

```
def palindrome(string):
'''
Returns the longest palindrome in string.
'''
reverse = string[::-1]
winner = ''
if string == reverse:
return string
sources = [(string, reverse), (reverse, string)]
for source_a, source_b in sources:
for window in range(1, len(source_a) - 1):
string_a = source_a[:-window]
string_b = source_b[window:]
results = compare(string_a, string_b)
for result in results:
if len(result) > len(winner):
print result
winner = result
return winner
def compare(string_a, string_b):
'''
Compares two strings of equal length and finds any common strings between
the two.
'''
result = []
# True if a commonality is being extracted. This flag lets us know when to
# insert a new value into result.
found = False
for index in range(len(string_a)):
if string_a[index] == string_b[index]:
if not found:
result.append('')
found = True
result[-1] += string_a[index]
else:
found = False
return result
print palindrome('zbbybab')
```

```
def updateMax(palinIndex, palinLen, maxPalinLen, maxPalinIndex, i):
if palinLen>maxPalinLen:
maxPalinLen=palinLen
maxPalinIndex=palinIndex
palinLen=0
palinIndex=i
return palinIndex, palinLen, maxPalinLen, maxPalinIndex
def longestPalindrome(s):
pi=0 #Palindrome Index
pl=0 #Palindrome Length
lpl = -1 #Longest Palindrome Index
lpi = -1 #Longest Palindrome Length
for i, c in enumerate(s):
if i==0:
continue
if s[pi]==c:
if (pi>0):
pi-=1
pl+=2
else:
pi, pl, lpl, lpi=updateMax(pi, pl, lpl, lpi, i)
else:
pi, pl, lpl, lpi=updateMax(pi, pl, lpl, lpi, i)
pi, pl, lpl, lpi=updateMax(pi, pl, lpl, lpi, i)
return s[lpi+1:lpi+lpl+1]
s="ldsfkjoeiwrjwelskzdjfsdaasdfgfdfghjkllkjhgfdlkfherqriuthekdfsnvgkjwnoirjsefdq"
print longestPalindrome(s)
```

Whaqt about below solution, let me know if any bug is there, inputs tested are

LongestPalindrome("aabcbcdab");

LongestPalindrome("aaaaa");

LongestPalindrome("abbba");

LongestPalindrome("this is a a uyt this is a a si si");

LongestPalindrome("abeeddddeabe");

public static void LongestPalindrome(string a)

{

string isPalindrome = "";

string largestPalindrome = "";

int j, k;

for (int i = 0; i < a.Length - 1;i++)

{

k = i + 1;

j = i - 1;

if (j >= 0 && k < a.Length)

{

if (a[i] == a[j] && a[i] == a[k])

{

j--; k++;

}

}

if (j > 0 && k < a.Length)

{

if (a[i] == a[j])

j--;

else if (a[i] == a[j])

{

k++;

}

}

while (j >= 0 && k < a.Length)

{

if (a[j] != a[k])

break;

else

{

j--;

k++;

}

isPalindrome = a.Substring(j + 1, k - j - 1);

if (isPalindrome.Length > largestPalindrome.Length)

{

largestPalindrome = isPalindrome;

}

}

}

Console.WriteLine(largestPalindrome);

}

```
public static int[] getLongest(String str){
char[] data = str.toCharArray();
int[] index = new int[data.length];
int[] buffer = new int[256]; //store pre index
int max = 0;
int[] span = new int[2];
for(int i = data.length - 1; i >= 0; i--){
index[i] = buffer[data[i]] == 0 ? -1 : buffer[data[i]];
buffer[data[i]] = i;
}
for(int i = 0; i < index.length && index[i] != -1 ; i++){
int cur = i;
int j = index[i];
while(j != -1){
for(; j != -1; j = index[j]){
if(isPaloindromes(data,cur,j) == true){
if(max < j - cur + 1){
max = j - cur + 1;
span[0] = cur;
span[1] = j;
}
}
}
int tmp = cur;
index[tmp] = -1;
cur = index[cur];
j = cur == -1 ? -1 : index[cur];
}
}
return span;
}
public static boolean isPaloindromes(char[] data, int i, int j){
int mid = (i + j) / 2;
for(int k = 0; k < mid; k++){
if(data[i + k] != data[j - k])
return false;
}
return true;
}
```

```
public class HelloWorld{
public static void main(String []args){
String test="mestts,youoygg,mesccsem";
int len=test.length();
char[] strtest=new char[len];
int maxcount=0;
for(int i=0;i<len;i++)
{
char a=test.charAt(i);
strtest[i]=a;
}
if (len<2)
{
System.out.print(1);
}
else
{
for(int i=0;i<len;i++)//main char position,get char chain length
{
for (int j=1;j<=len-i;j++)//chains' length,j is length
{
char[] unit=new char[j];
for (int k=0;k<j;k++)//get string of the char chain
{
unit[k]=strtest[i+k];
}
String truetest=String.valueOf(unit);//string express;
int lenoftrue=truetest.length();
int lockt=0;
if(lenoftrue==1)
{
lockt=1;
}
else
{
for (int count=0;count<lenoftrue/2;count++)//for compare
{
if(truetest.charAt(count)==truetest.charAt(lenoftrue-count-1))
{
lockt=1;
continue;
}
else
{ lockt=0;
break;
}
}
}
if(lockt==1&&lenoftrue>=maxcount)
{
maxcount=lenoftrue;
}
}
}
System.out.print(maxcount);
}
}
}
```

```
public class HelloWorld{
public static void main(String []args){
String test="mestts,youoygg,mesccsem";
int len=test.length();
char[] strtest=new char[len];
int maxcount=0;
for(int i=0;i<len;i++)
{
char a=test.charAt(i);
strtest[i]=a;
}
if (len<2)
{
System.out.print(1);
}
else
{
for(int i=0;i<len;i++)//main char position,get char chain length
{
for (int j=1;j<=len-i;j++)//chains' length,j is length
{
char[] unit=new char[j];
for (int k=0;k<j;k++)//get string of the char chain
{
unit[k]=strtest[i+k];
}
String truetest=String.valueOf(unit);//string express;
int lenoftrue=truetest.length();
int lockt=0;
if(lenoftrue==1)
{
lockt=1;
}
else
{
for (int count=0;count<lenoftrue/2;count++)//for compare
{
if(truetest.charAt(count)==truetest.charAt(lenoftrue-count-1))
{
lockt=1;
continue;
}
else
{ lockt=0;
break;
}
}
}
if(lockt==1&&lenoftrue>=maxcount)
{
maxcount=lenoftrue;
}
}
}
System.out.print(maxcount);
}
}
}
```

public static String getLongestPalindrome (String source)

{

if (source == null || source.isEmpty ())

{

return "";

}

int sourceLen = source.length ();

if (sourceLen == 2)

{

if (source.charAt (0) == source.charAt (1))

{

return source;

}

return "" + source.charAt (0);

}

int startMarker, endMarker;

String palindrome = "";

for (int i = 2; i < source.length (); i++)

{

startMarker = 0;

endMarker = sourceLen;

if (source.charAt (i) == source.charAt (i - 1))

{

if (i <= sourceLen / 2)

{

endMarker = 2 * i;

}

else

{

startMarker = 2 * i - sourceLen;

}

}

else if (source.charAt (i) == source.charAt (i - 2))

{

if (i <= sourceLen / 2)

{

endMarker = 2 * i - 1;

}

else

{

startMarker = 2 * i - sourceLen - 1;

}

}

palindrome = getBestPalindrome (source.substring (startMarker, endMarker), palindrome);

}

return palindrome;

}

public static String getBestPalindrome (String source, String palindrome)

{

source = source.toUpperCase ();

if (source == null || source.isEmpty ())

{

return palindrome;

}

String myPalindrome = source;

for (int i = (source.length () / 2); i > 0; i--)

{

if (source.charAt (i - 1) != source.charAt (source.length () - i))

{

myPalindrome = source.substring (i, source.length () - i);

break;

}

}

if (palindrome.length () <= myPalindrome.length ())

{

return myPalindrome;

}

return palindrome;

}

I choose maintainability over performance until performance testing shows the code to be a bottleneck.

```
public string FindLongestPalindrome(string sInput)
{
int i = 0;
int j = 0;
int k = 0;
int l = 0;
int lower=0;
int upper=0;
char [ ]input = sInput.ToCharArray();
int len = sInput.Length;
// Odd length Palindromes
while (i < len && j < len)
{
k = i;
l = j;
while ((k >= 0 && l < len) && (input [k] == input [l]))
{
if ((upper - lower) <= (l - k))
{
lower = k;
upper = l;
}
k--;
l++;
}
i++;
j++;
}
// Even length Palindromes
i = 0;
j = 1;
while (i < len && j < len)
{
k = i;
l = j;
while ((k >= 0 && l < len) && (input [k] == input [l]))
{
if ((upper - lower) <= (l - k))
{
lower = k;
upper = l;
}
k--;
l++;
}
i++;
j++;
}
return(sInput.Substring(lower, (upper-lower+1)));
}
```

{{package mic01;

public class LongestPalindrome {

public static void main(String[] args) {

String dummy = "AAABBGFF ili ollo benmio ooloo eo sadkjansd evbnbve eikdo ooooooooookoooooooooo";

System.out.println(letsDoThis(dummy));

}

private static String letsDoThis(String dummy) {

String result = null;

int max = 0;

String[] a = dummy.split(" ");

for(int i=0; i<a.length; i++){

if(isPalindrome(a[i])){

if(a[i].length() > max)

result = a[i];

}

}

return result;

}

private static boolean isPalindrome(String string) {

int length = string.length();

if(length % 2 == 0)

return false;

else{

for(int i=0; i<length/2; i++){

if(string.charAt(i) != string.charAt(length-i-1)){

return false;

}

}

}

return true;

}

}

}}

detalied explanation can be found at www.math.tau.ac.il/~haimk/seminar02/suffixtrees.ppt

- vairaghi January 26, 2008