Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
I think Manacher algo can solve this in O(n):
(I treat single character as palindrome)
int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();
int ret = 0;
vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci - i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i - pl >= 0){
if(ns[i + pl] != ns[i - pl]) break;
else pl++;
}
pl -= 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}
return ret;
}
I have tried it with O(n^2) the best I could get..
#include <stdio.h
/*
*
*/
void main()
{
char test[] = "xzyabcbaty";
//first check where the possible palindrom exists
int i, counter=0, j;
int start[10], end[10], possible_candidates=0;
for ( i=0 ; i<sizeof(test)-1 ; i++)
{
for (j=i+1 ; j < sizeof(test) ; j++)
{
if (test[i] == test[j])
{
start[counter] = i;
end[counter] = j;
possible_candidates++;
counter++;
}
}
}
//check if we have any possibility of palindrom
if (counter)
{
int num_of_substring = 0;
for (i=0 ; i < possible_candidates ; i++)
{
if (is_palindrom(test, start[i], end[i]))
{
num_of_substring++;
}
}
printf("Total number of substrings %d", num_of_substring);
}
else
{
printf("Nothing found");
}
}
/*
* palidrom checking function with O(n/2)
*/
int is_palindrom(char* string, int start, int end)
{
int i, j=0;
for (i=start ; i < end ; i++)
{
if (string[i] != string[end-j])
{
return 0;
}
j++;
}
return 1;
}
The complexity is O(n^2) + O(n^2) which is 2(O(n^2) => O(n^2)
Follow the below steps:
1. Reverse the string and add it to the original string. For eg if the string given is 'banana' take is as 'banana#ananab'
2. Make a suffix array of this string.
3. Put all the suffixes in a hashmap and sort the hashmap to avoid duplicate entries, you can even use arrays.
4. Now find the common prefix in the adjacent strings. Iterate through the hasmap or array created in last point. If you want youcan store this common prefix in a seperate array p. The array p contains all the palindrome string. You can count all the palindrome greater than any length or the longest palindrome.
My idea is to use DP.
s[i,j]= 1 if s[i+1,j-1]=1 && A[i]=A[j], where i+1<=j-1
if A[i]=A[i+1] if i=j-1
0 otherwise
sum=0;
for(i=n; i>=0;i--)
{
for(j>=n;j>=i;j--)
{
if(i==j)
S[i,j]=1;
else
{
if(j=i+1)
{
if(A[i]==A[j])
s[i,j]=1;
else
s[i,j]=0;
}
else
{
if(s[i+1,j-1]==1 && A[i]==A[j])
s[i,j]=1;
else
s[i,j]=0;
}
}
sum += s[i,j];
}
}
#include<stdio.h>
int checkpalindrom(char *s,char *s1)
{
while(s<s1)
if(*s++!=*s1--)
return 0;
return 1;
}
void main()
{
char string[30],c;
int i=0,j=0,n=0;
printf("\n Enter the Msg :- ");
gets(string);
printf("\n Palindram substring are as follow \n\n");
for(i=0,j=0;string[i];i++)
{
if(string[i]==' ' || string[i]=='\t')
{ c=*(string+i);
*(string+i)='\0';
if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);
*(string+i)=c;
j=i+1;
}
}
if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);
}
input and output as follow ....
Enter the Msg :- hi madam and mom gud day
Palindram substring are as follow
1) madam
2) mom
#include "stdio.h"
#include "string.h"
int main() {
char * str = "abababbaa";
printf("hello world from panindrom!\n");
printf("%s has %d panindrom\n",str, getNumberOfPanindrom(str));
}
int getNumberOfPanindrom(char * str) {
return center_in_even_position(str) + center_in_odd_position(str);
}
int center_in_odd_position(char * str) {
int i,j = 0;
int count = 0;
int size = strlen(str);
for( i = 0; i < size; i++)
{
for( j = 1; j <= min(i, size - i - 1); j++)
{
if(str[i-j] == str[i+j])
count ++;
else
break;
}
}
return count;
}
int center_in_even_position(char * str) {
int i, j = 0;
int count = 0;
int size = strlen(str);
for( i = 0; i < size; i ++)
{
for (j = 0; j < size - i - 1; j++)
{
if(str[i-j] == str[i+j+1])
count ++;
else
break;
}
}
return count;
}
int min(int a, int b) {
return ((a > b) ? b : a);
}
This solution works in O(n+p) where n is the length of string and p is the length of palindrom patterns. In worst case it would be O(n^2)
check it:
/a.out "baab check aa abc zxz it adda hhh "
./a.out " baab check aa abc zxz it adda hhh "
./a.out
#include <iostream>
using namespace std;
int palindromesCount(char *input)
{
int countpalindromes=0;
int wordStart=0,wordEnd=0;
int charStart,charEnd;
while(input[wordStart] != '\0') {
if(input[wordStart] != ' ') {
for(wordEnd = wordStart; input[wordEnd] != ' ' & input[wordEnd] != '\0'; wordEnd++); wordEnd--;
charStart = wordStart;
charEnd = wordEnd;
while( ((charEnd-charStart) > 0) & (input[charEnd]==input[charStart]) ) { charStart++; charEnd--;};
if( (charEnd-charStart) <=0 ) countpalindromes ++;
wordStart = wordEnd+1;
}
else wordStart++;
}
return countpalindromes;
};
main(int argc, char *argv[])
{
if(argc>1) cout << palindromesCount(argv[1]) << endl;
}
you can use a suffix array to get a O(nlogn) algorithm
first construct a new string S+'#'+S' which # is not in char set of S and S' is the reversion of S. Then build a suffix array and calculate the longest common prefix.
sum up each i < len(S) , LCP(Rank[i],Rank[2n-i]) you got the final answer.
if the LCP use a segment tree then each query take O(lgn) time. so the total complexity of the algorithm is O(nlogn)
int countPalindromes(const string& str)
{
int N = str.size();
vector< vector<int> > dp(N, vector<int>(N, 0));
int cnt = 0;
for (int i=0; i < N; i++) {
cnt += (dp[i][i] = 1);
}
for (int k=1; k < N; k++)
for (int j=k, i=0; j < N; j++, i++)
cnt += (dp[i][j] = str[i] == str[j] & dp[i+1][j-1];
return cnt;
}
/*
About Program: Finding all the possible substrings of a given string as well as finding the palindrome substrings in it.
Date: 19/07/2012
Author: Aditya Dhaniwala
*/
#include<stdio.h>
#include<conio.h>
#include<string.h>
main()
{
int i,j,k,flag=0,c=0,num=0,num2=0;
char str[200],strcopy[200]={"\0"},stringconcat[200]={"\0"},temp[2]={"\0"},temp2[2]={"\0"};
printf("Enter the string : ");
gets(str);
for(i=0;i<strlen(str)-1;i++)
{
temp[0]=str[i];
strcat(stringconcat,temp);
for(j=i+1;j<strlen(str);j++)
{
temp2[0]=str[j];
strcat(stringconcat,temp2);
printf("%s\n",stringconcat);
num2++;
strcpy(strcopy,stringconcat);
strrev(strcopy);
flag=strcmp(stringconcat,strcopy);
if(flag==0)
{
printf("Palindrome string = %s\n",strcopy);
c=1;
num++;
}
}
for(k=0;k<200;k++)
{
stringconcat[k]='\0';
strcopy[k]='\0';
}
}
if(c==0)
printf("CANNOT FIND A PALINDROME SUBSTRING");
printf("\nTotal number of palindromes of the main string and its substring = %d\nTotal number of substrings possible=%d",num,num2);
getch();
}
using dynamic programming.
int Dp(std::string & str) {
int n = str.size();
std::vector<std::vector<int> > dp(n, std::vector<int>(n, 0));
int rs = 0;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n - k; i++) {
if (k == 0) dp[i][i + k] = 1;
else if (k == 1) dp[i][i + k] = str[i] == str[i + k] ? 1 : 0;
else {
if (dp[i + 1][i + k - 1] && str[i] == str[i + k]) dp[i][i + k] = 1;
}
if (dp[i][i + k] == 1) rs++;
}
}
return rs;
}
O(n^2) algo:
require 'pp'
str = "and";
res = []
count = 0
pp str.length
(0..(str.length-1)).each{|i|
res[i] = []
(0..(str.length-1)).each{|j|
if i>j
res[i][j] = -1
elsif i == j
res[i][j] = 1
count += 1
else
if ((res[i][j-1] == 1) and (str[j] == str[i]))
res[i][j] = 1
count += 1
else
res[i][j] = 0
end
end
}
}
pp res
pp count
Here is my O(n) solution. The code uses extra storage to track the number of characters matched at the current position based on the number of characters matched at the previous position. The matching logic simply compares the current position to the even & odd offsets based on the number of matches seen in each case previously. The insights I had were
1. It seemed very similar to the KMP substring problem
2. Each palindrome of length n had n/2 smaller palindromes
3. Once characters start matching, the palindrome will continue to expand until it stops at which point a new palindrome starts from that index
Please comment if you find bugs.
Thanks
#define array_elements(_a) (sizeof((_a)) / sizeof((_a)[0]))
#define MAX_LENGTH 4096
#define PRINT_PALINDROME_SUBSTRINGS 1
void
print_palindrome_substring(
char *s, int start, int end, char *message, int count
)
{
printf("%s [%d]: ", message, count);
while (start <= end) {
printf("%c", s[start]);
start++;
}
printf(".\n");
}
int
count_palindrome_substrings(
char *s
)
{
int pred_even[MAX_LENGTH];
int pred_odd[MAX_LENGTH];
int i;
int count;
int off;
pred_even[0] = 0;
pred_odd[0] = 0;
i = 1;
count = 0;
while (s[i] != 0) {
off = i - 1 - 2 * pred_even[i - 1];
if (off >= 0 && s[off] == s[i]) {
pred_even[i] = pred_even[i - 1] + 1;
count++;
#if PRINT_PALINDROME_SUBSTRINGS
print_palindrome_substring(s, off, i, "even", count - 1);
#endif // PRINT_PALINDROME_SUBSTRINGS
} else {
pred_even[i] = 0;
}
off = i - 1 - 2 * pred_odd[i - 1] - 1;
if (off >= 0 && s[off] == s[i]) {
pred_odd[i] = pred_odd[i - 1] + 1;
count++;
#if PRINT_PALINDROME_SUBSTRINGS
print_palindrome_substring(s, off, i, "odd", count - 1);
#endif // PRINT_PALINDROME_SUBSTRINGS
} else {
pred_odd[i] = 0;
}
i++;
}
return count;
}
int
main(
int argc,
char **argv
)
{
int i;
char *palindrome_substrings_test[] = {
"abbba",
"abbabcddcbaefghihgfe" };
for (i = 0; i < array_elements(palindrome_substrings_test); i++) {
printf(
"count_palindrome_substrings(%s) = %d.\n",
palindrome_substrings_test[i],
count_palindrome_substrings(palindrome_substrings_test[i]));
}
}
int palidrome_count(const char *a, int n)
{
int i;
int len;
int count = n;
int **p = (int **)malloc(sizeof(int *) * n);
for (i = 0; i < n; ++i) {
p[i] = (int *)malloc(sizeof(int) * (n+1));
memset(p[i], 0, sizeof(int) * (n+1));
p[i][0] = p[i][1] = 1;
}
for (len = 2; len <= n; ++len) {
for (i = 0; i + len < n; ++i) {
p[i][len] = ((a[i] == a[i + len - 1]) ? 1 : 0) & p[i+1][len-2];
count += p[i][len];
}
}
for (i = 0; i < n; ++i) {
free(p[i]);
}
free(p);
return count;
}
I think Manacher algo can solve this in O(n), I implement two algos:
1. longestPalindrome is O(n) using Manacher
2. partition is O(n^2) using 2-order DP
#include <stdio.h>
#include <iostream>
#include "climits"
#include "vector"
#include "cstring"
#include <sstream>
#include "cstdlib"
#include "map"
#include "algorithm"
#include "cmath"
#include "queue"
#include "stack"
using namespace std;
class Solution {
public:
int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();
int ret = 0;
vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci - i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i - pl >= 0){
if(ns[i + pl] != ns[i - pl]) break;
else pl++;
}
pl -= 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}
return ret;
}
int partition(string s) {
int n = s.size();
vector< vector< bool > > palindromeMatrix(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
palindromeMatrix[i][i] = true;
}
int ret = n;
for (int margin = 1; margin < n; margin++) {
for (int i = 0; i < n - margin; i++) {
int j = i + margin;
if ((i + 1 > j - 1 || palindromeMatrix[i + 1][j - 1])
&& s[i] == s[j]) {
palindromeMatrix[i][j] = true;
palindromeMatrix[j][i] = true;
ret += 1;
}
}
}
return ret;
}
};
int main(int argc, char** argv) {
Solution ss;
string s = "abaaba";
cout << ss.longestPalindrome(s) << endl;
cout << ss.partition(s) << endl;
}
I did it by getting all substrings and checking them for palindromes, O(n^3). Interviewer said, it can be done better in time.
#include<stdio.h>
int checkpalindrom(char *s,char *s1)
{
while(s<s1)
if(*s++!=*s1--)
return 0;
return 1;
}
void main()
{
char string[30],c;
int i=0,j=0,n=0;
printf("\n Enter the Msg :- ");
gets(string);
printf("\n Palindram substring are as follow \n\n");
for(i=0,j=0;string[i];i++)
{
if(string[i]==' ' || string[i]=='\t')
{ c=*(string+i);
*(string+i)='\0';
if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);
*(string+i)=c;
j=i+1;
}
}
if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);
}
Here is O(N^2) solution.
1. Count all even length palindromes.
2. Count all odd length palindromes.
3.return count.
Can someone post the implementation of suffix array?
- Aashish July 08, 2012