CareerCup

Reverse the string
Find the maximum substring

Wrong !!!!

abcdgdba

Reverse it : abcdgdba

"ab" matches , but it is not a palindromic substring .

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

array index out of bound exception in first if stmnt of while loop.
The algo fails for first case when start = i =0

I didn't understand whats wrong with reversing of a string, since we are getting ab which is the actually longest palindrome ab***ba abba..?? correct me if i m wrong..

"ab" is a palindrome ???????????

Ibnipun is correct. But has to be improved.

1. Find the LCString of A and reverse of A.
2. You get say string B.
3. If B is a palindrome, only then does A have a palindrome (i.e of length atleast two, well, every letter is a palindrome of itself :) ). Otherwise no palindrome.

Ibnipun is correct.

1. Find the LCString of A and reverse of A.
2. You get say string B.
3. If B is a palindrome, only then does A have a palindrome (i.e of length atleast two, well, every letter is a palindrome of itself :) ). Otherwise no palindrome.

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

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