## Microsoft Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
4
of 4 vote

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

Comment hidden because of low score. Click to expand.
0

``````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]);
}
}

}``````

Comment hidden because of low score. Click to expand.
0

``````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));
}

}

}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

This can be solved using "Suffix Tree".

Comment hidden because of low score. Click to expand.
0

Are you sure? more details, thx

Comment hidden because of low score. Click to expand.
2
of 4 vote

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,str,...,str[i].
beginIndex[i] = beginning index of the longest palindrome in substring having characters str,str,...,str[i].

len = 1;
beginIndex = 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;
len = 1;
if(str.charAt(0) == str.charAt(1))
{
bIndex = 0;
len = 2;
}
else
{
bIndex = 1;
len = 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);

}

Comment hidden because of low score. Click to expand.
0

code has bugs. how about "abeeddddeabe"?

Comment hidden because of low score. Click to expand.
0

not correct.

Comment hidden because of low score. Click to expand.
2
of 2 vote

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>

typedef struct Node Node;
struct Node {
int len;
Node* next;
};

Node* insertNode(Node* head, Node* node) {
return node;
}

Node* createNode(int len) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->len = len;
return newNode;
}

Node* insertNum(Node* head, int len) {
}

void printReverse(Node* node) {
if (node != NULL) {
printReverse(node->next);
printf("%d ", node->len);
}
}

printf("\n");
}

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;
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;
}``````

Comment hidden because of low score. Click to expand.
0

@Ryan: Could you write some comments in the main function which would help to understand the algorithm.
Link of Haskell code you provided is fine. Due to C/C++ background, I am neither able to understand its code nor the algo given there due to its complex explanation.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes, LC String does not work.
Ex: string:abcdecba
reverse:abcedcba
LCS:abc/cba

Comment hidden because of low score. Click to expand.
0

Very good counter example. Thanks.

Comment hidden because of low score. Click to expand.
0

I didn't understand: isn't abc/cba the longest palindromic substring for the ex.?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Nope, it isnt.

Comment hidden because of low score. Click to expand.
0

IT is a valid example.. The palindromic substring is not contiguous

Comment hidden because of low score. Click to expand.
0

A. reverse string.
B. get LC substrings. in this case ABC & CBA.
C. check if they are palindromes.
D. And thats it.
Complexity is O (n^2). Lawyered.

Comment hidden because of low score. Click to expand.
0
of 1 vote

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?

Comment hidden because of low score. Click to expand.
0

Not equivalent. Find comments below from Spec on Mar 10th.

Comment hidden because of low score. Click to expand.
0

The method is still feasible if we check the location of the common substrings after we find them. For the substring to be a palindrome, the start position of the substring in the original string should be symmetrical with the ending position of the substring in the reversed one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use suffix tree or suffix array.

for(i=0;i<strlen(A);i++)
c[i]=&A[i];
for(i=0;i<strlen(A');i++)
c'[i]=&A'[i];

for(i=0;i<strlen(A);i++)
{
get the longest common substring from the head of
c[i],c'[n-i-1]
c[i+1],c'[n-i-1]
}

Comment hidden because of low score. Click to expand.
0
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

o what a

Comment hidden because of low score. Click to expand.
0

No. That should be longest substring, and the time complexity still be O(n2).

Comment hidden because of low score. Click to expand.
0
of 0 vote

It is Longest Common Substring (Need to be contiguous)

Comment hidden because of low score. Click to expand.
0
of 0 vote

01234567890010987654321 will return 123456789

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

awesome!

Comment hidden because of low score. Click to expand.
0

not awesome. that doesn't work.

Comment hidden because of low score. Click to expand.
0

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();

}

Comment hidden because of low score. Click to expand.
0

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();

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

yeah ok, like this is what you will write on a white board. How many whiteboards will you need? Get realistic.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

i think we can solve this using dynamic programing...

n is the length of str
if(i<n){
str[i]==str[n] i++,n--;store i,n;
else
call func with i+1,n
call func with i,n-1
}

i think u got my sol..

Comment hidden because of low score. Click to expand.
0
of 0 vote

DP solution:

int F(char* a, int n)
{
if(n==1) return 1;

int k = F(a, n-1);
if(IsPalindrom(a, n-2k-2, n))
k++;

return k;
}

thoughts?

Comment hidden because of low score. Click to expand.
0
of 0 vote

?

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just have an idea to reduce few calculations ..
1. Maintain a hash table..keep track of all characters which appear more den once .( store their indices )
2.You can chek for all these indices ..this will possible reduce chekin for all the possibilities ..waitin for a better soln :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Agreed with sameerud, but essential addition: there are 2 types of palindromes:
something like 'aba' and 'abba'.

So for every symbol we should test those two possibilities, not only the first one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Agreed with sameerud, but essential addition: there are 2 types of palindromes:
something like 'aba' and 'abba'.

So for every symbol we should test those two possibilities, not only the first one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Input String is s1, Reverse the string to s2.
Use Dynamic Programming to find the longest common substring. That gives u the result!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

longest common subsequence not substring

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(size(s1)+size(s2)) it is!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++){

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse + LCSubstring

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

12345 is absolutely the longest palindrome in your string. Whats wrong with it?

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

how about "is" "is" ? I thought they were the longest palindrome...

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@Vijgan:
Moreover the longest common palindrome is one that is present in the exact same manner both in the original string and its reverse.In your case "si si" in the reversed string is present as "is is" in the original string.So this is not a palindrome at all.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My views:

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?

Comment hidden because of low score. Click to expand.
0

Ur idea is good one...i successfully implemented it ..thnx..order is O(n^2)

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess this is one of the best possible solution...
But, usually this problem is coupled with another objective to find all the palindromes in a string and also to find the longest palindrome..in this case instead we can use a static variable and find the longest palindrome...

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The example string should be 'ABMOCECXYYX'.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nice comment KB. Then I guess I have no choice but to iterate it 'N' times and update a static variable, so that we access and get the longest palindrome.

What do you think?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Create suffix trees of the original and reversed strings. Sort the suffixes separately. Find max length between suffix array from one string to that of the reversed.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

The Sucker who was taking my interview did asked. I can bet he could have ever written that himself.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Suffix trees has O(n) time to look.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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,

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]

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

:)

Comment hidden because of low score. Click to expand.
0

good one !!! implemented successfully...100% working ...thnx

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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??

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Oops! I meant O(n^2)
Loop structure will just be nested loops

``````i = 0 -> n
j = i-> n``````

Comment hidden because of low score. Click to expand.
0

It is not longest common substring .. it is longest common subsequence between the string and its reverse.

So for abcdecba, it will be abcdcba or abcecba

Comment hidden because of low score. Click to expand.
0
of 0 vote

My cents:

Building suffix trees is not a bad idea. We can get that in O(nlogn) time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

go suck dick

Comment hidden because of low score. Click to expand.
0

u 2

Comment hidden because of low score. Click to expand.
0

Hi Vishal,

You solution will not work always... You can try it on RACECAR........

Comment hidden because of low score. Click to expand.
0

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 ...

Comment hidden because of low score. Click to expand.
0

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 ...

Comment hidden because of low score. Click to expand.
0

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....

Comment hidden because of low score. Click to expand.
0

This won't work for HTTKNOM

Comment hidden because of low score. Click to expand.
0

this won't work for HTTKNOM

Comment hidden because of low score. Click to expand.
0

Stupid solution.

APQP
PQPA

XOR, none are zeroes, but PQP is the longest palindrome.

Comment hidden because of low score. Click to expand.
0

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]:
result.append('')
found = True
result[-1] += string_a[index]
else:
found = False

return result

from sys import argv
print palindrome(argv)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

If i'm not mistaken would'nt this be O(n^3)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just reverse the string and find the largest substring in both the strings. O(n^2).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

the longest palindrome is infact OWO !!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

It's complexity will be O(n). I have a working code for this. if anybody want.

Comment hidden because of low score. Click to expand.
0

test case: abcddcbe

does it work?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

this looks like a good solution

Comment hidden because of low score. Click to expand.
0
of 0 vote

@gagdeep what does the 'i' signify ??

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you show the working code by which you arrived O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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...........

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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...........

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

the simplest way is O(N^2)
if applying suffix tree time can be reduced to O(NlogN)

Comment hidden because of low score. Click to expand.
0

the simplest way is O(N^2)
if applying suffix tree time can be reduced to O(NlogN)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

finding-the-longest-palindromic-substring-in-linear-time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

It's awesome to see people using suffix tree and O(nlogn) at the same time !!

Comment hidden because of low score. Click to expand.
0

And why not?

There are simpler implementations of suffix tree which are O(nlogn).

Because implementing suffix tree can be so complex, ppl might choose to lose some run time over the possible maintenance headaches.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My suggestion is that any approach of O(n^2) time and O(1) space that can be well explained and you can write working code during an interview would suffice!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Reverse the string and find biggest substring.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

No need for such complex algorithms !!!

I was asked this question, I proposed trying all combination (O(n^2) I think) he looked convinced with that approach.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int main()
{
char *p,*q,*r,*found;
int i=0;
int max=0;
for(p=a;*p!='\0';p++)
{
q=p; r=a+strlen(a);
while(q<r)
{
if(*q==*r)
{i+=2;
q++; r--;
}
else
{
i=0;
r--; q=p;
}
}

if(i>max) {max=i; found=p;}
}
if(q==r) max=max+1;
std::cout<<max<<*found;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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]);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

Comment hidden because of low score. Click to expand.
0

Complexity here is O(n^3).

Comment hidden because of low score. Click to expand.
0
of 0 vote

int _tmain(int argc, _TCHAR* argv[])
{
char p,*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;
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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

A very good O(n2) easy to follow code is available in
technicalypto.com/2010/02/find-all-possible-palindromes-in-string

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
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");
}``````

Comment hidden because of low score. Click to expand.
0

nice !!!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]:
result.append('')
found = True
result[-1] += string_a[index]
else:
found = False

return result

print palindrome('zbbybab')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0

output: dfghjkllkjhgfd

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int[] getLongest(String str){
char[] data = str.toCharArray();
int[] index = new int[data.length];
int[] buffer = new int; //store pre index
int max = 0;
int[] span = new int;

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 = cur;
span = 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)));
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

{{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;
}

}

}}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.