Microsoft Interview Question Software Engineer / Developers
Let the given string be S.
create a new string R (R is the reverse of S)
now create a general suffix tree with these two strings S# and R$.
The longest path from the root to a node which has its children nodes $ and # is the longest palindrome.
we can use KMP as well for in this method. use S$R word to find longest palindrom. wher R is reverse of string S.
This is a java code which runs in O(n).
steps:
1. First tokenize the string.
2. For each token u r getting find the length and reverse the string and check palindrome or not
3. Finally compare the length is max or not and print the string.
public class LongPalin {
public int strPalin(String token)
{
int len = token.length();
String reverse = new StringBuffer(token).reverse().toString();
if(token.equalsIgnoreCase(reverse))
return len;
else
return -1;
}
public static void main(String[] args) {
String sent = " civic Dewed Malayalam rotavator redder";
String longpalin = null;
StringTokenizer Tok = new StringTokenizer(sent);
int n=0, maxlen =0;
LongPalin lp = new LongPalin();
while (Tok.hasMoreElements())
{
String token1 = Tok.nextToken();
int len = lp.strPalin(token1);
if(maxlen < len )
{
maxlen = len;
longpalin = token1;
}
}
System.out.println("longest palindrome ="+ longpalin);
}
}
@anonymous
The whole sentence is processed in a single pass
so the time complexity is O(n). can u plz explain why the time complexity is not O(n)
inside loop u have to reverse and compare - these operations are O(n), so total complexity is O(n^2)
for O(n) we have to check every char only once.
we can maintain a stack and after we read every char peek the stack and if the char is same as stack it will be a middle of palindrome . keep track the size of stack.(A)
then change mode and ever new char pop the stack and if the trend breaks means new char is not same as the top in stack, palindrome ended here; A-StackCurrentSize multiple 2
is the length of it, now start pushing chars to stack again....
this need max O(n) extra space for stack and solves in O(n) time.
same we can do for odd palindrome too...
please review if you find some bug in it...
1. assume original string is S
2. reverse each word in the sentence and store it in string R
3. now compare each word in S, R and find longest matching word
this can be done in O(n)
Forgot to mention, step 2 can be done in O(n) time using some extra space.
Reverse the whole sentence, then split it and copy the words from last.
Ex :
Assume string is "I am aabaa"
reverse the string "aabaa ma I"
split it - "aabaa", "ma", "I"
now, copy this words (from last) to new string,
I ma aabaa
but I guess u are making an assumption here that the palindrome will be a complete word; while the question statement does not necessarily support this assumption.
I don't think you solution work correctly.
Assume the given string is 123aba56, then the correct answer should be aba.
The reverse string is 65aba321, then how will you compare?
I think an O(n) solution may require to build a suffix tree on S#1R#2 within O(n), and then find the latest common ancestor
of #1 and #2.
Another solution would be build the suffix Array on T=S#R@ and a RMQ to calculate the longest common prefix for the suffix Array with O(nlgn) time, then you can check the longest common prefix of T[i..2n] and T[2n-i] (if the length of palindrome is odd, similar in an even case) for all the i, the query can be done in O(1) with RMQ, and the time to find out i is O(n), which together gives you a O(nlnn) + O(n) = O(nlgn) algorithm
Convolve string with reverse(string), the point at which the area is max under the curve is the longest palindrome.
- Anonymous December 29, 2010