Amazon Interview Question
Country: United States
There is a method called suffix array to solve this problem.
Idea is:
For each position i, find the longest continuous common part in two side (before i and after i). like
cbabc
for position 2 (count from 0), the left and right longest common part is 2.
Then the problem is actually to find the longest common part of suffix(i) and prefix(i).
Example:
s1 : aababcbabb
For position 2, we should find the longest common prefix of
babcbabb
baa
which is ba, so the longest palindrome centered at position 2 would be aba.
To find this longest prefix, we cannot use a naive enumeration, we should sort all of suffix and reverted prefix together.
Now the problem is how to sort all suffix and reverted prefix, actually we can first revert the original string (refer as s1'), and append it to s1, like following:
s1#s1' (the # is used as a separator)
then we just sort the suffix in this converted string (because suffix in s1' is reverted prefix of s1), the separator is used to judge whether suffix belongs to s1 or s1'.
To sort the suffix of this appended string, there is a technique called doubling, and it could be found by searching Suffix array.
You can use Manacher's algorithm for this :
String getLargestPalString(String S) {
int T = preProcess(S); // Method arranges '#' in between the char in S, before and after the string
int C = 0;
int R = 0;
int n = T.length();
int[] P = new int[n];
for(int i = 1; i < n-1; ++i) {
int i_mirror = 2*C-i;
P[i] = (R > i) ? (max(P[i_mirror], R-i)) : 0;
while(T.charAt(i+P[i]+1) == T.charAt(i-P[i]-1))
P[i]++;
if(R-i < P[i]) {
R = i+P[i];
C = i;
}
}
//Finding max from P to get largest Pal substring
int max = -1;
int index = -1;
for(int i = 0; i < n; ++i) {
if(max < P[i]) {
max = P[i];
index = i;
}
}
int C = i/2;
int start = C-max/2;
int end = C+max/2-(i&1);
return S.substring(start, end);
}
Scala:
def rmDuplicates(s: String): String = s.toList match {
case Nil => ""
case c :: rest => c + rmDuplicates(rest.filterNot(e => e == c).mkString)
}
def uniqueSubstr(s: String, xs:List[String]):List[String] = s.toList match {
case Nil => xs
case c :: rest => uniqueSubstr(rest.mkString, (c::(rest.takeWhile(x => x != c))).mkString :: xs)
}
scala> val v = uniqueSubstr("dabcade", Nil).map(s => rmDuplicates(s)).sortWith((x,y) => x.length > y.length)(0)
v: String = bcade
public string largestPalindrome(string input)
{
int i, j, k, len = input.Length, maxLengthTillNow = 0;
string palindromeString = string.Empty;
for (i = 1; i < len; ++i)
{
// for even length palindrome
if (input[i - 1] == input[i])
{
j = i - 2;
k = i + 1;
//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j--;
k++;
}
//compare with prev max
if (maxLengthTillNow < (k - j - 1))
{
maxLengthTillNow = k - j - 1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}
// for odd length palindrome
if ((i + 1 < len) && input[i - 1] == input[i + 1])
{
j = i - 2;
k = i + 2;
//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j--; k++;
}
//compare with prev max
if (maxLengthTillNow < (k - j - 1))
{
maxLengthTillNow = k - j - 1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}
}
return palindromeString;
}
With O(n) this is possible using suffix tree. Search for previous posts of this questions you'll find it there.
- Grr1967 November 25, 2012