Adobe Interview Question
Software Engineer / DevelopersWrong !!!!
abcdgdba
Reverse it : abcdgdba
"ab" matches , but it is not a palindromic substring .
Reverse of abcdgba = abgdcba
Max substring = dgd which is a palindrome
One step I missed here is after finding all the substring check for palidrome as well
1. traverse each character left to right.
2. compare character i to i+1 and i+2 (since palindromes can be odd or even)
3. in a loop, compare i-n with i+1+n in sequence until the chars don't match.
4. Keep track of maxLength and maxIndex.
5. Build in early exits and proper null checks.
public string FindLongestPalindrome(string item)
{
if (item==null || item==string.empty) return string.empty;
int maxLength = 1;
int maxIndex = 0;
for (int i=0; i < item.Length - maxLength /*earlyExit*/; i++)
{
for (int j=1; j < 3; j++)
{
if (i+j >= item.length) break;
if (item[i] != item[i+j]) continue;
int start=i;
int end = i+j;
while (start > 0 && end < item.length - 1)
{
if (item[start-1] != item[end+1]) break;
start--;
end++;
}
if (end-start > maxLength)
{
maxIndex = start;
maxLength = end-start;
}
}
return item.SubString(maxIndex, maxLength);
}
Let S is given string, T is reverse of S. Build a generalized suffix tree GST (see Wikipedia) for S and T. Search for the longest common prefix in GST.
example: S = 1232, T = 2321
suffixes of S = {1232,232,32,2}, and of T = {2321,321,21,1}
"232" is the longest common prefix. Even though number of possible suffixes in GST can be O(n^2), it can be collapsed to represent in compact way. As compact GST can be be built in O(n) time with O(n) space, it's probably optimal solution (surely, not easy to code with space/time constraint).
Plz correct if I'm wrong.
here is some pseudocode
i hope it solves the problem
as i see it is a DP problem
I have given a recursive solution , memoisation will give O(N^2) time complexity
int palindrome(char str[],int start,int end,int len)
{ if(len==1) return 1;
else if((str[start]==str[end]) && palindrome(str,start+1,end-1,len-1))
return 1;
else return 0;
}
struct start_end longest_palindrome(char str[],int start,int end,int len)
{ if(palindrome(str,start,end,len)
return start,end
else
{
}
here is some pseudocode
i hope it solves the problem
as i see it is a DP problem
I have given a recursive solution , memoisation will give O(N^2) time complexity
int palindrome(char str[],int start,int end,int len)
{ if(len==1) return 1;
else if((str[start]==str[end]) && palindrome(str,start+1,end-1,len-1))
return 1;
else return 0;
}
struct start_end longest_palindrome(char str[],int start,int end,int len)
{ if(palindrome(str,start,end,len)
return start,end
else
{ ret=longest_palindrome(str,start+1,end,len-1);
if(ret!=NULL)
return ret;
else
{ ret=longest_palindrome(str,start+1,end,len-1);
if(ret!=NULL)
return ret;
}
}
return NULL;
}
here is some pseudocode
i hope it solves the problem
as i see it is a DP problem
I have given a recursive solution , memoisation will give O(N^2) time complexity
int palindrome(char str[],int start,int end,int len)
{ if(len==1) return 1;
else if((str[start]==str[end]) && palindrome(str,start+1,end-1,len-1))
return 1;
else return 0;
}
struct start_end longest_palindrome(char str[],int start,int end,int len)
{ if(palindrome(str,start,end,len)
return start,end
else
{ ret=longest_palindrome(str,start+1,end,len-1);
if(ret!=NULL)
return ret;
else
{ ret=longest_palindrome(str,start+1,end,len-1);
if(ret!=NULL)
return ret;
}
}
return NULL;
}
I hope this is understandable . bOTH functions need to be memoized..
Please correct me ,if i am wrong
sry correction
in the longest palindrome fucntion
the second recursive call should be
ret=longest_palindrome(str,start,end-1,len-1);
This is modification done over the previous concept. This works fine.
struct start_end{
int s;
int e;
};
int palindrome(char str[],int start,int end,int len)
{
if(len==1 || start>end) return 1;
else if((str[start]==str[end]) && palindrome(str,start+1,end-1,len-2)) return 1;
else return 0;
}
struct start_end longest_palindrome(char str[],int start,int end,int len)
{
start_end ret1={0,0},ret2={0,0};
static start_end tvar={0,0};
if(len>1)
if(palindrome(str,start,end,len)){start_end temp;temp.s=start;temp.e=end;return temp;}
else
{
ret1=longest_palindrome(str,start+1,end,len-1);
ret2=longest_palindrome(str,start,end-1,len-1);
if(ret1.e-ret1.s>ret2.e-ret2.s)
tvar=ret1;
else tvar=ret2;
}
return tvar;
}
var pal = ['a','b','c','d','c','b','a'];
var reversePal = pal.reverse();
var count = 0;
for( i=0; i < pal.length; i++ )
{
var newPal = pal.slice(0,i);
var newReversePal = reversePal.slice(0,i);
alert( newPal + " : " + newReversePal );
if( newPal.toString() == newReversePal.toString() )
{
count = i;
}
}
alert( count);
a O(n^2) solution
int palindrome(int a[], int n)
{
int LongestSoFar = 0, start, end, count=0,lstart,lend;
for(int i=0;i<n;i++)
{
if(count>LongestSoFar)
{
LongestSoFar = count;
lstart = start;
lend = end;
}
count = 0;
for(int p = i,q=i;p>=0&&q<n;p--,q++)
{
if(a[p]!=a[q])
break;
else
{
count++;
start = p;
end = q;
}
}
}
for(i=lstart;l<=end;l++)
count<<a[i];
retun count;
}
string largestPal(string input_str)
{
string isPal = "";
string largest = "";
int j, k;
for(int i = 0; i < input_str.length() - 1; ++i)
{
k = i + 1;
j = i - 1;
// starting a new interation
// check to see if even pal
if(j >= 0 && k < input_str.length()) {
if(input_str[i] == input_str[j])
j--;
else if(input_str[i] == input_str[j]) {
k++;
}
}
while(j >= 0 && k < input_str.length())
{
if(input_str[j] != input_str[k])
break;
else
{
j--;
k++;
}
isPal = input_str.substr(j + 1, k - j - 1);
if(isPal.length() > largest.length()) {
largest = isPal;
}
}
}
return largest;
}
Reverse the string
- DashDash July 06, 2010Find the maximum substring