Microsoft Amazon Interview Question Software Engineer / Developers




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

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

- vairaghi on January 26, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- MaYanK on August 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Another Coder on January 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

This can be solved using "Suffix Tree".

- Anonymous on December 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you sure? more details, thx

- dddonghl on October 16, 2012 | Flag
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[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);

}

- Gopal Krishna on December 14, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

code has bugs. how about "abeeddddeabe"?

- biwatershed on December 30, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

not correct.

- karpur on May 14, 2012 | Flag
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>

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

- Ryan on February 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- monish.gupta1 on November 06, 2011 | Flag
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

- Spec on March 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very good counter example. Thanks.

- Anonymous on March 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bird on March 16, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on April 04, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nope, it isnt.

- G on May 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on September 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- AP on November 15, 2010 | Flag
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?

- selluck on November 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on March 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on February 15, 2010 | Flag
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]
}

- anonymous on November 14, 2008 | Flag Reply
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.

- newera on December 08, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

o what a

- Anonymous on September 24, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dddonghl on October 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is Longest Common Substring (Need to be contiguous)

- Anonymous on December 08, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

01234567890010987654321 will return 123456789

- reverse the string and use longest common string does not work on February 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on April 04, 2009 | Flag
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.

- Anonymous on March 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome!

- uwcse on November 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

not awesome. that doesn't work.

- Mahesh on October 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- wondergirl on December 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- Anonymous on December 10, 2010 | Flag
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;
}

- cristi.vlasceanu on May 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on April 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

http://wiki.answers.com/Q/Is_there_any_way_to_find_the_largest_palindrome_in_a_string

- Anonymous on June 01, 2009 | Flag Reply
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.

- pranjal5215 on July 07, 2009 | Flag Reply
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..

- Appy on July 19, 2009 | Flag Reply
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?

- Anonymous on August 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?

- caffeine_coder on November 06, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pbalaramtej on December 03, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pbalaramtej on December 03, 2009 | Flag
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 :)

- naive on November 06, 2009 | Flag Reply
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.

- larrr on November 06, 2009 | Flag Reply
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.

- larrr on November 06, 2009 | Flag Reply
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!

- radio on November 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ryan on February 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rusho on March 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

longest common subsequence not substring

- Anonymous on October 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on November 07, 2009 | Flag Reply
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++){


}

}

- another guy on November 07, 2009 | Flag Reply
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

- another guy on November 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse + LCSubstring

- geniusxsy on November 08, 2009 | Flag Reply
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).

- Ran on November 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 on November 11, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon on November 12, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ran on November 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vijgan on November 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ran on November 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ran on November 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- particularraj on November 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Neevan on January 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Neevan on January 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bobby on November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Antonio on February 28, 2013 | Flag
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...

- anonymous on November 09, 2009 | Flag Reply
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.

- KBSorter on November 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The example string should be 'ABMOCECXYYX'.

- KBSorter on November 09, 2009 | Flag Reply
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?

- particularraj on November 09, 2009 | Flag Reply
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.

- Anonymous on November 09, 2009 | Flag Reply
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.

- Anonymous on November 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Frustoo on November 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suffix trees has O(n) time to look.

- Raj on November 10, 2009 | Flag Reply
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,

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]

- Tejas on November 10, 2009 | Flag Reply
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.

:)

- beto on November 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Neevan on January 21, 2012 | Flag
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.

- Ankush on November 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Hari on November 12, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Cheema on December 26, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- Cheema on December 26, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- subsequence not substring on October 18, 2011 | Flag
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.

- particularraj on November 12, 2009 | Flag Reply
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

- Vishal on November 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

go suck dick

- Anonymous on November 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

u 2

- Anonymous on November 19, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Vishal,

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

- kunalgaind on November 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on November 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on November 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- whoami on December 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't work for HTTKNOM

- Anonymous on January 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this won't work for HTTKNOM

- fgh on January 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Stupid solution.

APQP
PQPA

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

- Anonymous on January 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- llvllatrix on July 25, 2012 | Flag
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)

- parry on November 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on November 16, 2009 | Flag
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).

- Anonymous on November 16, 2009 | Flag Reply
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

- trey on November 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the longest palindrome is infact OWO !!

- Dan on December 15, 2009 | Flag
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.

- gagdeep on November 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gagdeep on November 17, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

test case: abcddcbe

does it work?

- Anonymous on November 17, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gagdeep on November 17, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this looks like a good solution

- Vinya on July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@gagdeep what does the 'i' signify ??

- bala on November 20, 2009 | Flag Reply
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)

- nalin on November 20, 2009 | Flag Reply
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...........

- kunalgaind on November 20, 2009 | Flag Reply
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

- Thiyanesh on November 20, 2009 | Flag Reply
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...........

- kunalgaind on November 20, 2009 | Flag Reply
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;
            }
         }
      }
   }

- kcoder on November 21, 2009 | Flag Reply
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;
}

- Anonymous on November 21, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on November 23, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- asuran on November 23, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- bewnet on November 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Longest thread of answers to Longest palindrome finding :)

- anon on November 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

could not post the link. google for this. the first link has a good solution

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

- SK on December 23, 2009 | Flag Reply
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 !!

- Anonymous on January 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on January 07, 2010 | Flag
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!

- c on February 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reverse the string and find biggest substring.

- Anonymous on March 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- hary on March 08, 2010 | Flag
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.

- Anonymous on March 08, 2010 | Flag Reply
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)

- Tarun Phaugat on March 09, 2010 | Flag Reply
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;
}
}
}

- ManoX on April 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
char a[]="abcdaeeadabb";
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;
}

- O(n^2) on April 11, 2010 | Flag Reply
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]);

}

- Dee on April 13, 2010 | Flag Reply
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.

- Nithish on April 18, 2010 | Flag Reply
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>

- Anonymous on May 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity here is O(n^3).

- Amol on June 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on August 01, 2010 | Flag Reply
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);
}

- Mahesh on October 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Amit on January 10, 2011 | Flag
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;
}

- Amit on January 10, 2011 | Flag Reply
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];
}

- reen on February 24, 2011 | Flag Reply
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

- Anonymous on June 13, 2011 | Flag Reply
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[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");
}

- sergey.a.kabanov on January 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice !!!!

- Neevan on January 21, 2012 | Flag
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]:
            if not found:
                result.append('')
                found = True
            result[-1] += string_a[index]
        else:
            found = False

    return result

print palindrome('zbbybab')

- llvllatrix on July 25, 2012 | Flag Reply
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)

- Will on October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

output: dfghjkllkjhgfd

- Will on October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Read about Manacher's Algorithm

- Alphalpha on October 30, 2012 | Flag Reply
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);



}

- Looking2ChangeJob on November 18, 2012 | Flag Reply
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[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;
	}

- jialiang.bao on August 04, 2013 | Flag Reply
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)));
}

- RED on February 23, 2011 | Flag Reply
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;
}

}

}}

- orhancanceylan on June 12, 2012 | Flag Reply


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More