Microsoft Interview Question Software Engineer in Tests
0of 0 votesHow to find the longest palindrome is a string
we can start from the left end of the string and gradually move towards right end checking at every step its neighbors(both cases for odd and even length palimdrome) and if criteria for a palindrome if met then spread further in left and right direction to check if they also meet the criteria ,keep speading at each step until criteria fails(then record the start and end index of this palindrome string).. keep doin this till u reach the right end of the string.
hope my logic is convincing for most of the people who have posted the solution or the comments and in case u find any flaw then just let me know ...
reverse the string and then it becomes the longest common subsequence problem b/w (string, reverse string)
can be solved in O(n)
huge mistake, above will not be a solution ... LCS need not find consecutive characters
longest common subsequence is not solvable in O(n) it is solvable in O(n^2) using dynamic pgmg... longest common substring is an easier version of the same problem and can also be solved in O(n^2). However using a suffix tree to find the longest common substring is d best way and solves it in O(n)...
#include <stdio.h>
#include<string.h>
int main()
{
int i,j,a[256],max=0,c=0,w,u,k,p;
char s[30];
printf("enter the string\n");
gets(s);
for(i=0;i<256;i++)
{
a[i]=0;
}
for(i=0;s[i]!='\0';i++)
{
a[s[i]]++;
}
i=0;
while(s[i]!='\0')
{
j=strlen(s)-1;
if(a[s[i]]>1)
{
while(j!=i)
{
if(s[j]==s[i])
{
k=j-1;
p=i+1;
c=0;
while((k>p)&&(s[k]==s[p]))
{
k=k-1;
p=p+1;
c=c+1;
}
if(k<=p)
{
if(c>max)
{
max=c;
w=i;
u=j;
}
a[s[i]]--;
break;
}
}
j--;
}
}
i++;
}
if(max>0){
printf("the required plaindrome is:\t");
while(w<=u)
{
putchar(s[w]);
w++;
}
}
else{
printf("there isnt any palindrome");
}
return 0;
}
there is slight modification:
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,a[256],max=0,c=0,w,u,k,p;
char s[30];
printf("enter the string\n");
gets(s);
for(i=0;i<256;i++)
{
a[i]=0;
}
for(i=0;s[i]!='\0';i++)
{
a[s[i]]++;
}
i=0;
while(s[i]!='\0')
{
j=strlen(s)-1;
if(a[s[i]]>1)
{
while(j!=i)
{
if(s[j]==s[i])
{
k=j-1;
p=i+1;
c=0;
while((k>=p)&&(s[k]==s[p]))
{
k=k-1;
p=p+1;
c=c+1;
}
if(k<=p)
{
if(c>max)
{
max=c;
w=i;
u=j;
}
a[s[i]]--;
break;
}
}
j--;
}
}
i++;
}
if(max>0){
printf("the longest palindrome is:\t");
while(w<=u)
{
putchar(s[w]);
w++;
}
}
else{
printf("there isnt any palindrome");
}
return 0;
}
there is slight modification:
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,a[256],max=0,c=0,w,u,k,p;
char s[30];
printf("enter the string\n");
gets(s);
for(i=0;i<256;i++)
{
a[i]=0;
}
for(i=0;s[i]!='\0';i++)
{
a[s[i]]++;
}
i=0;
while(s[i]!='\0')
{
j=strlen(s)-1;
if(a[s[i]]>1)
{
while(j!=i)
{
if(s[j]==s[i])
{
k=j-1;
p=i+1;
c=0;
while((k>=p)&&(s[k]==s[p]))
{
k=k-1;
p=p+1;
c=c+1;
}
if(k<=p)
{
if(c>max)
{
max=c;
w=i;
u=j;
}
a[s[i]]--;
break;
}
}
j--;
}
}
i++;
}
if(max>0){
printf("the longest palindrome is:\t");
while(w<=u)
{
putchar(s[w]);
w++;
}
}
else{
printf("there isnt any palindrome");
}
return 0;
}
assume every char a possible center of a plindrom save current max length of palindrom seen so far and continue..its a o(n2) soln but for an interview its good enough i blv..
pls let me know if it fails for any csae.
thanks
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,a[256],max=0,c=0,w,u,k,p, mc, l, st, e;
char s[30];
printf("enter the string\n");
gets(s);
mc = 1;
l = strlen(s);
c = 1; st = e = 0;
for(i = 0;i<l;i++)
{
j = i-1;k = i+1; c = 1;
while(1)
{
if(j>=0 && k<l && (s[j] == s[k]))
{
j--;
k++;
c+=2;
continue;
}
if(k<l && (s[i] == s[k]))
{
k++;
c+=1;
continue;
}
else if(mc<c)
{
if(c==2)
st = j;
else
st = j+1;
e = k-1;
mc = c;
}
break;
}
}
if(mc <=1)
printf("there isnt any palindrome");
else
{
printf("%d", mc);
for(;st<=e;st++)
printf("\t%c", s[st]);
}
getchar();
return 0;
}
Build a suffix tree for concatenation of string with its reversal...O(n) time and space. Should be pretty easy from there to check for palindromes. See for example Gusfield's book on algorithms for strings and sequences...lots of stuff on suffix trees for string problems. Good thing to know how to apply, then maybe mumble that the details on building suffix trees are complicated and it's been a while
#include <stdio.h>
char *getLongestPallindrome(char *);
int checkPallindrome(char *);
char *extract(char *,int,int);
void main()
{
char *str="cdeedc";
printf("%s",getLongestPallindrome(str));
}
char *getLongestPallindrome(char *s)
{
char *ostr=(char *)malloc(sizeof(s));
int i=0,j,k=0;
while(s[i]!=NULL)
{
k=i;
j=strlen(s)-1;
while(k<=j)
{
if(s[k]==s[j])
{
if(checkPallindrome(extract(s,k,j)) && strlen(extract(s,k,j))>strlen(ostr))
{
strcpy(ostr,extract(s,k,j));
break;
}
}
//k++;
j--;
}
i++;
}
return ostr;
}
int checkPallindrome(char *str)
{
int flag=0,f=0,l=strlen(str)-1;
while(f<=l)
{
if(str[f]!=str[l])
{
flag=1;
break;
}
f++;
l--;
}
if(flag==1)
return 0;
return 1;
}
char *extract(char *s,int f,int l)
{
int i=0;
char *os=(char *)malloc(sizeof(s));
while(f<=l)
{
os[i++]=s[f++];
}
os[i]=NULL;
return os;
}
Python Code
import logging
def findLargestPallindrome(inputString):
stringLen = len(inputString)
index =0
palindromes= []
longestPallindrome = ''
while stringLen>index:
palLen =1
while (index + (palLen*2))<=stringLen:
splitPart = inputString[index+palLen:index+palLen*2]
if inputString[index:palLen+index] == splitPart[::-1] and (palLen*2)>len(longestPallindrome) :
longestPallindrome =inputString[index:index+palLen*2]
palLen +=1
index +=1
return longestPallindrome
print findLargestPallindrome('ssaaddaassssaaddaass')
1. Declare an array of size 256 (represents 256 ASCII chars) say A
2. Fill the array with 0's initially.
3. Read the given string and update the count in array at the ascii position.
Eg. if 'a' then A[97] = 1. If found again just make A[97] = 2.
4. Read the array A and form the palindrome accordingly.
Time complexity: O(n) - Reading array of size n + O(1) - Reading array of size 256
== O(n)
Space complexity: O(1)
- manu October 02, 2010//Complexity is O(n2) with extra storage to build the 2 d matrix //Other Optimizations we can do is as we discussed that we dont need to store the reversed string //If input[i] == input[j] and i == 0 OR j == 0 (i.e. first row or first col) then insert 1 //If input[i] == input[j] and i != 0 and j != 0 then increment the diagonal value i.e. (i-1, j-1) + 1 // If input[i] != input[j] insert 0 private static string GetLongestPalindromeSecondAlgo(string input1, string input2) { //Storage to build the 2d matrix int[,] num = new int[input1.Length, input2.Length]; //maxlength encountered so far int maxlength = 0; int LastSubBegin = 0; //Output stringbuilder parameter to store the string StringBuilder re = new StringBuilder(); for (int i = 0; i < input1.Length; i++) { for (int j = 0; j < input2.Length; j++) { //If char matches if (input1[i] == input2[j]) { //First Row or first Column if (i == 0 || j == 0) { num[i, j] = 1; } else { //Increment the diagonal value num[i, j] = num[i - 1, j - 1] + 1; } if (num[i, j] > maxlength) { maxlength = num[i, j]; int thisSubBegin = i - num[i, j] + 1; if (thisSubBegin == LastSubBegin) { re.Append(input1[i]); } else { LastSubBegin = thisSubBegin; re = new StringBuilder(); re.Append(input1.Substring(LastSubBegin, num[i, j])); } } } else { //If char are different num[i, j] = 0; } } } return re.ToString(); } private static string GetReversed(string str) { StringBuilder output = new StringBuilder(); for (int i = str.Length - 1; i >= 0; i--) { output.Append(str[i]); } return output.ToString(); } //--------------------------------------------------------Second Algo--------------------------------------------------------------------// //BruteForce Complexity is O(n3) public static string GetLongestPalindrome(string input) { //Variable to keep max length of palindrome so far int lengthSofar = 0; //Variable to keep longest palindrome so far string resultstring = string.Empty; //Loop to get substring which starts with i char for (int i = 0; i < input.Length;i++) { string substring = input[i].ToString(); for (int j = i+1; j < input.Length;j++) { substring += input[j]; //Check is the substring is palndrome or not if(IsPalindrome(substring)) { if (lengthSofar < substring.Length) { lengthSofar = substring.Length; resultstring = substring; } } } } return resultstring; } //Method to check whether string is palindrome or not public static bool IsPalindrome(string input) { if (input == null) return false; if (input.Length == 1) return true; int halflen = input.Length / 2; int len = input.Length - 1; //Basically it compares the first char and last char until it reached the halflength of the string for (int i = 0; i < halflen; i++) { if (input[i] != input[len]) { return false; } len--; } return true; } //****************************************************3rd Most efficient Algorithm***************************************************// public static string GetLongestPalindromeEff(string str) { if (str == null || str.Length == 0) { return null; } if (str.Length == 1) { return str; } string longest = ""; string strsofar = ""; for (int i = 0; i < str.Length - 1; i++) { if (str[i] == str[i + 1]) //its a 2 char palindrome { strsofar = GetSize(str, i, i + 1); } if (i + 2 < str.Length && str[i] == str[i + 2]) { strsofar = GetSize(str, i + 1, i + 1); } if (strsofar.Length > longest.Length) { longest = strsofar; } } return longest; } private static string GetSize(string input, int start, int end) { StringBuilder str = new StringBuilder(); int count = 0; int index = 0; for(int i = start, j = end; i >= 0 && j < input.Length; i--,j++ ) { if (input[i] != input[j]) { Console.WriteLine(input.Substring(index, count)); return input.Substring(index, count); } index = i; count = j - i + 1; } Console.WriteLine(input.Substring(index, count)); return input.Substring(index, count); } }