Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
That is to find the longest palindrome substring. This question cannot be solved in linear time!
let the sting of length(n)
the for each char index x we check(assuming it is the center element in palindrone) that for i<x<j till there is a palindrone (max comparison n/2)
if index char[x] ==char[ x--] ||char[x]==char[x++] then we need to do another search assuming length of palin is even x is one of the mid elements another (n/2) comparison at max
now if we know [i,j] the limits of palindrone with x as the centre element
then number of palinds = summation of over all elements( if(j-i == even)? (j-i) /2 : (j-j+3)/2)
complexity = n*(3n/2) = n^2
As i read more on this , this is similar to Manacher's algorithm which can construct[i,j] in linear time and also inserts # to make sure all palin substring are odd length .. so
yes the complexity can be reduced to O(n)
O(n) solution
string preprocess(string s)
{
if(s.length()==0)
return "^$";
string z = "^";
for(int i=0;i<s.length();i++)
{ z +="#";
z = z.append(s.substr(i,1));}
z+="#$";
return z;
}
int find123(string s)
{
string z;
int *count = (int *)malloc(s.length() *sizeof(int)* 2 + 3*sizeof(int));
int L=0,R=0,C=0,sum=0;
z = preprocess(s);
for(int i=1;i<z.length();i++)
{
int index = 2*C-i;
count[i] = (R>i) ? min(R-i,count[index]):0;
while(i+1+count[i]<z.length()&&z[i+1+count[i]]==z[i-1-count[i]])
count[i]++;
if(i+count[i]>R)
{
C=i;
R = i+count[i];
}
if(count[i] > 1)
sum+=(count[i]+1)/2;
else
sum+=count[i];
}
return sum;
}
First solutions that comes to mind:
C++:
bool isPalindrome(char *arr,int left, int right){
if(right-left==0){
return true;
}
for(int i=0;i<=(left+right)/2;++i){
if(arr[i]!=arr[right-i])
return false;
}
return true;
}
int allPalindromes(char *arr){
int length=strlen(arr);
if(length<=1) return length;
int count=0;
for(int i=0;i<length;++i){
for(int j=i;j<length;++j){
if(isPalindrome(arr,i,j){
count++;
}
}
}
return count;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Banana {
public static void main(String[] args) throws IOException {
BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
String line = inp.readLine();
for(int i = 0 ; i <line.length() ; i++){
for(int j = i+1 ; j <=line.length();j++){
String banana = line.substring(i, j);
if(ispalin(banana)){
System.out.println(banana);
}
}
}
}
private static boolean ispalin(String banana) {
// TODO Auto-generated method stub
for(int i = 0 ; i < banana.length()/2 ; i++){
if(banana.charAt(i) != banana.charAt(banana.length()-i-1)){
return false;
}
}
return true;
}
}
The solution seems reasonable but it tooks O(n^3)
I think we can reduce it to O(n^2) if we utilize the following property
S[i,j] is palin if S[i-1,j+1] is palin and S[i]==S[j]
A simpler approach, O(N2) time and O(1) space:
public static int find(String inputText) {
if (inputText == null) {
System.out.println("Input cannot be null!");
return 0;
}
// ODD Occuring Palindromes
int len = inputText.length();
int palindromes = len;
for (int i = 1; i < len - 1; i++) {
for (int j = i - 1, k = i + 1; j >= 0 && k < len; j--, k++) {
if (inputText.charAt(j) == inputText.charAt(k)) {
palindromes++;
System.out.println(inputText.subSequence(j, k + 1));
} else {
break;
}
}
}
// EVEN Occuring Palindromes
for (int i = 1; i < len - 1; i++) {
for (int j = i, k = i + 1; j >= 0 && k < len; j--, k++) {
if (inputText.charAt(j) == inputText.charAt(k)) {
palindromes++;
System.out.println(inputText.subSequence(j, k + 1));
} else {
break;
}
}
}
return palindromes;
}
Also, we can reduce amount of code and cycles duplicating if we will perform both odd and even check simultaneously:
String input = "abbba";
int count = input.length();
int length = count;
for (int i = 1; i < length - 1; i++) {
for (int j = i - 1, m = i, k = i + 1; k < length; j--, m--, k++) {
boolean found = false;
if (m >= 0 && (input.charAt(m) == input.charAt(k))) {
count++;
found = true;
}
if (j >= 0 && (input.charAt(j) == input.charAt(k))) {
count++;
found = true;
}
if (!found) {
break;
}
}
}
System.out.println("Total count: " + count);
This is a O(n) time solution solved recursively but has space complexity
public class Palindrome {
private ArrayList<String> palindromPosib = new ArrayList<String>();
public void findPalin(){
String p = "abba";
palindrome(p,0);
for (String t : palindromPosib){
System.out.println(t);
}
}
public ArrayList<String> palindrome(String s, int index){
if(index == s.length()){
ArrayList<String> empty = new ArrayList<String>();
empty.add("");
return empty;
}
else{
ArrayList<String> subs = palindrome(s, index+1);
ArrayList<String> newSubs = new ArrayList<String>();
//newSubs.addAll(subs);
newSubs.add("");
StringBuilder st = new StringBuilder();
for(String t: subs){
st.append(t);
st.append(s.charAt(index));
if(isPalindrome(st.toString())){
palindromPosib.add(st.toString());
}
newSubs.add(st.toString());
st.delete(0, st.length());
}
return newSubs;
}
}
public boolean isPalindrome(String a){
return a.equals(reverse(a));
}
public String reverse(String a){
System.out.println("__"+a);
char t[] = a.toCharArray();
char r[] = new char[t.length];
for (int i = t.length-1,j=0; i >= 0&&j<t.length; i --, j++){
r[j]= t[i];
}
System.out.println("++"+String.copyValueOf(r));
return String.copyValueOf(r);
}
//abaca
public static void main(String[] args) {
Palindrome p = new Palindrome();
p.findPalin();
}
}
function allpalindromes(str) {
var len = str.length;
//case 1 div at gap "abc^cba" i=3
for(var i=1;i<len;i++) {
var bond = Math.max(i, len-i);
for(var j=1;j<=bond;j++) {
if(str[i-j] === str[i+j-1]) {
console.log(str.substring(i-j, i+j));
} else {
break;
}
}
}
//case 2 div at char i= index of the char
for(var i=1;i<len;i++) {
console.log(str.charAt(i));
}
for(var i=1;i<len;i++) {
var bond = Math.max(i-1, len-i-1);
for(var j=1;j<=bond;j++) {
if(str[i-j] === str[i+j]) {
console.log(str.substring(i-j, i+j+1));
} else {
break;
}
}
}
}
//test
allpalindromes("abccba")
I print all the palindromes the ranther than calculate the count
if replace the print statement with count increase, the time complexity should be O(n^2)
function palindrome(inputString){
var palindromes = [];
for(var i = 0; i < inputString.length; i++){
for(var j = 1; j <= (inputString.length - i); j++){
if(inputString.substring(i, j+i) == inputString.substring(i, j+i).split("").reverse().toString().replace(/,/gm,"")){
palindromes.push(inputString.substring(i, j+i));
}
}
}
return palindromes;
}
/**
*
* @author Marcelo Filho
* @email marcelolfilho@gmail.com
* @facebook facebook.com/idemax.green
*
*/
public class PalindromePratice {
/**
* Buffer of results to be displayed.
*/
private static StringBuilder strB;
/**
* Main called by Java.
*
* @param args
*/
public static void main( final String[] args ) {
PalindromePratice.palindrome( "abba" );
}
/**
* Add some {@link String} to result buffer.
*
* @param value
*/
private static void addToBuffer( final String value ) {
if ( PalindromePratice.strB == null ) {
PalindromePratice.strB = new StringBuilder();
}
PalindromePratice.strB.append( value );
PalindromePratice.strB.append( ',' );
}
/**
* Display results in buffer.
*/
private static void displayResults() {
if ( PalindromePratice.strB != null ) {
PalindromePratice.strB.deleteCharAt( PalindromePratice.strB.length() - 1 );
System.out.println( PalindromePratice.strB.toString() );
}
}
/**
* Scan for palindromes.
*
* @param value
* {@link String} with two or more chars.
*/
private static void palindrome( final String value ) {
PalindromePratice.palindrome( value, true );
PalindromePratice.displayResults();
}
/**
* Scan for palindromes.
*
* @param value
* {@link String} with two or more chars.
* @param recursive
* If algorithm has to scan recursively.
*/
private static void palindrome( final String value, final boolean recursive ) {
final int valueLen = value.length();
if ( valueLen > 0 ) {
final int halfValueLen = valueLen / 2;
boolean isPalindrome = true;
if ( recursive ) {
int wordSize = 1;
for ( int i = 0; i < valueLen; i++ ) {
while ( ( wordSize < valueLen ) && ( i <= wordSize ) ) {
PalindromePratice.palindrome( value.substring( i, wordSize++ ), false );
}
wordSize = 1;
}
}
for ( int i = 0, j = ( valueLen - 1 ); i <= halfValueLen; i++, j-- ) {
isPalindrome = value.charAt( i ) == value.charAt( j );
if ( !isPalindrome ) {
break;
}
}
if ( isPalindrome ) {
PalindromePratice.addToBuffer( value );
}
}
}
}
package com.egain.platform.module.kb.workflow;
public class NumberOfParliments
{
/**
* @param args
*/
public static void main(String[] args)
{
System.out.println(findNumberOfPalindromes("abbc"));
}
public static int findNumberOfPalindromes(String a)
{
int sum = 0;
if (a.length() > 0)
{
char c = a.charAt(0);
for (int i = 0; i < a.length(); i++)
{
if (a.charAt(i) == c)
{
if (isPalindrome(a.substring(0, i + 1)))
{
sum = sum + 1;
}
}
}
return sum = sum + findNumberOfPalindromes(a.substring(1));
}
return 0;
}
private static boolean isPalindrome(String s)
{
if (s.length() == 1)
{
return true;
}
else if (s.length() > 1)
{
boolean bool = s.charAt(0) == s.charAt(s.length() - 1);
return bool && isPalindrome(s.substring(1, s.length() - 1));
}
else
return true;
}
}
package com.egain.platform.module.kb.workflow;
public class NumberOfParliments
{
/**
* @param args
*/
public static void main(String[] args)
{
System.out.println(findNumberOfPalindromes("abbc"));
}
public static int findNumberOfPalindromes(String a)
{
int sum = 0;
if (a.length() > 0)
{
char c = a.charAt(0);
for (int i = 0; i < a.length(); i++)
{
if (a.charAt(i) == c)
{
if (isPalindrome(a.substring(0, i + 1)))
{
sum = sum + 1;
}
}
}
return sum = sum + findNumberOfPalindromes(a.substring(1));
}
return 0;
}
private static boolean isPalindrome(String s)
{
if (s.length() == 1)
{
return true;
}
else if (s.length() > 1)
{
boolean bool = s.charAt(0) == s.charAt(s.length() - 1);
return bool && isPalindrome(s.substring(1, s.length() - 1));
}
else
return true;
}
}
{{
import java.util.ArrayList;
import java.util.List;
import org.junit.Assert;
import org.junit.Test;
public class Palindromes {
public int countPal(String str){
int count = 0;
for(int i=0; i<str.length(); i++){
for(int j=i+1; j<=str.length(); j++){
String term = str.substring(i, j);
if(isPal(term)){
count++;
}
}
}
return count;
}
public boolean isPal(String t){
StringBuilder rev = new StringBuilder();
char[] chars = t.toCharArray();
for(int i=chars.length-1; i>=0; i--){
rev.append(chars[i]);
}
return t.equals(rev.toString());
}
@Test
public void testCountPal(){
Assert.assertEquals(6, countPal("abba"));
Assert.assertEquals(1, countPal("b"));
Assert.assertEquals(3, countPal("bb"));
Assert.assertEquals(6, countPal("bbab"));
Assert.assertEquals(6, countPal("aacc"));
}
@Test
public void testIsPal(){
Assert.assertTrue(isPal("abba"));
Assert.assertTrue(isPal("aa"));
Assert.assertTrue(isPal("a"));
Assert.assertFalse(isPal("ac"));
}
}
}}
void combinationPalindrome(string ms)
{
int length = (int)ms.length();
int count = length;
int offset =1, left = 1, right = 0;
for(int i=1; i<length-1; i++)
{
while(true)
{
// Odd
if((i-offset >=0) && (i+offset < length) && ms[i-offset] == ms[i+offset])
{
cout<<endl<<"Odd "<<ms.substr(i-offset, 2*offset+1);
count++;
offset++;
}
//Even
else if((i-left >=0) && (i+right < length) && ms[i-left] == ms[i+right])
{
cout<<endl<<"Even "<<ms.substr(i-left, left+right+1);
count++;
left++;
right++;
}
else
{
offset = 1; right=0; left=1; break;
}
}
}
cout<<endl<<"Count "<<count;
}
this my working code, written in c
#include<stdio.h>
#include<string.h>
int main()
{
char c[] = "abba",*ptr = c,*c1,*c2;
int count = strlen(c);
while(*ptr != '\0') {
if(*ptr == *(ptr+1)) {
count = count +1;;
c1 = ptr - 1;
c2 = ptr + 2;
while(*c1 == *c2) {
count++;
c1++;
c2++;
}
}
if(*ptr == *(ptr+2)) {
count++;
c1 = ptr -1;
c2 = ptr + 3;
while(*c1 == *c2) {
count++;
c1++;
c2++;
}
}
ptr++;
}
printf("number of possible palindrome is the string = %d\n",count);
return 0;
}
1 #include<stdio.h>
2
3 int main(void)
4 {
5 char str[100];
6 int i, m, n, len, Count;
7
8 scanf("%s", str);
9
10 len = 0;
11 while(str[len])
12 len++;
13
14 Count = 0;
15
16 for(i = 0; i < len - 1; i++)
17 {
18 m = i;
19 n = i + 1;
20
21 while(m >= 0 || n < len)
22 {
23 if(str[m--] == str[n++])
24 Count++;
25 else
26 break;
27 }
28 }
29
30 printf("%d\n", Count);
31
32 return 0;
33 }
Expand along every possible center n-1 spaces and n-2 characters and traverse along both directions to see if characters on both the sides are equal. Total time is O(n2).
Example a|b|c|b|a|d
space centers are given by | symbol and character centers will be b,c,b,a..
Another algorithm is also possible in O(n) time, called manacher's algorithm. It is available on leetcode.com
This problem can be resolved using dynamic programming.
int Dp(std::string & str) {
int n = str.size();
int rs = 0;
std::vector<std::vector<int> > dp(n, std::vector<int>(n, 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] == 1 && str[i] == str[i + k]) dp[i][i + k] = 1;
}
if (dp[i][i + k] == 1) rs++;
}
}
return rs;
}
Dynamic programming : O(n²) in time and O(n) in space. Count separately palindromes depending on their lengths' parities.
Java :
static int substringPalindromesCount(String str) {
return str.length() + addedPalindromesCount(2, str) + addedPalindromesCount(3, str);
}
static int addedPalindromesCount(int start_id, String str) {
boolean[] is_palindrome = new boolean[str.length()];
Arrays.fill(is_palindrome, true);
int palindromes_count = 0;
for(int palindrome_length = start_id; palindrome_length <= str.length(); palindrome_length += 2) {
for(int palindrome_id = 0; palindrome_id <= str.length() - palindrome_length; palindrome_id++) {
is_palindrome[palindrome_id] = str.charAt(palindrome_id) == str.charAt(palindrome_id + palindrome_length - 1);
is_palindrome[palindrome_id] &= is_palindrome[palindrome_id + 1];
palindromes_count += is_palindrome[palindrome_id] ? 1 : 0;
}
}
return palindromes_count;
}
If the string is S and its reverse is S', consider the set of all suffixes of S and all suffixes of S'. For each suffix of S, append a special character $ to the end. For each suffix of S', append a special character # to the end. Now build the trie corresponding to this set of suffixes. In this tree, every node that has both special symbols as children corresponds to a palindromic substring of S (namely, that string obtained by concatenating the edges of the unique path from the node to the root of the tree).
There is a (very clever) algorithm for building a suffix tree in linear time.
Not the best thing ever, but here is a python implementation in a very simple manner:
def paly(input):
count = len(input)
for i in range(len(input)-1):
str = input[i]
for j in range(i+1,len(input)):
str += input[j]
if str == str[::-1]:
count += 1
return count
I could be solved using dynamic programming algorithm and extend the idea of given by shuaixin.david.
We will use this recurrence relation
P(i,j) = true if the string is palindrome between index i and j.
P(i,j) = P(i+1,j-1)
As a base case we to calculate all of the palindromes with length 1(for odd case) and 2(for even case). So, we will calculate P(i,i) and P(i,i+1) for all i.
Now, we will calculate the P(i,j) with growing difference between j. So, we will calculate P(i)(i+2) then P(i)(i+3) in this manner.
For all the P(i,j) we get true we will increment the count and return the count which is the all the substring palindromes possible.
Seriously they ask DP in phone screen? I think it's stupid, basically it asks do you know Manachers algorithm, if you know it, you know it, if you don't, there's no way you can figure that out by yourself in a 45mins phone interview. I guess they already decided they don't want to before the phone interview if they ask you this question.
Yes. I'm serious. Actually you never have 45 minutes to figure out the solution. I think you may have maximum 2-3 minutes. In addition, you cannot just thinking during these valued minutes as usual in a real situation. You need talk through about what is in your mind :) Therefore I asked whether the brute-force algorithm is ok for them.. The rest 40 minutes you need to write the code.
Anyway, Actually I think almost all the algorithm questions are the same. You need to know at least a really similar algorithm or set of the known algorithms which you need to modify and apply in the proper order. Anytime you can get such questions
I usually don't like when only one question is asked. If multiple short questions are asked then they can measure your knowledge in better way. Just imagine if you have 1 question like here in FB compared with 30 different questions. It's unlikely if you are good then you cannot answer 20-25 questions. But there is big chance to fail on one question. If they want to see real code they can ask 10-15 questions and a really basic algorithm to code. In other side if somebody could tell you the solution after 1 minute then it's unlikely that they would fail on the rest 40 minutes coding.. When I do interview I want to find the weak points of the candidates. if I realize that he knows the answer I think it would waste of time to listen the good solution during 40 minutes :) Anyway this is me and I don't work for Facebook :))
Seriously they ask DP in phone screen? I think it's stupid, basically it asks do you know Manachers algorithm, if you know it, you know it, if you don't, there's no way you can figure that out by yourself in a 45mins phone interview. I guess they already decided they don't want to before the phone interview if they ask you this question.
Seriously they ask DP in phone screen? I think it's stupid, basically it asks do you know Manachers algorithm, if you know it, you know it, if you don't, there's no way you can figure that out by yourself in a 45mins phone interview. I guess they already decided they don't want to before the phone interview if they ask you this question.
Seriously they ask DP in phone screen? I think it's stupid, basically it asks do you know Manachers algorithm, if you know it, you know it, if you don't, there's no way you can figure that out by yourself in a 45mins phone interview. I guess they already decided they don't want to before the phone interview if they ask you this question.
N^2, C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AllPalindromes
{
class Program
{
static void Main(string[] args)
{
if (args.Length != 1)
{
Console.WriteLine("AllPalindromes.exe <str>");
return;
}
for (int i = 0; i < args[0].Length; i++)
{
//Odd size
int begin = i;
int end = i;
string currentPalindrome = "";
do
{
if (begin == end)
{
currentPalindrome = args[0][begin].ToString();
}
else
{
currentPalindrome = args[0][begin].ToString() + currentPalindrome + args[0][end].ToString();
}
Console.WriteLine(currentPalindrome);
begin--;
end++;
} while (begin >= 0 &&
begin < args[0].Length &&
end >= 0 &&
end < args[0].Length &&
args[0][begin] == args[0][end]);
//Even size
begin = i;
end = i + 1;
if (end < args[0].Length &&
args[0][begin] == args[0][end])
{
currentPalindrome = "";
do
{
if (begin == end + 1)
{
currentPalindrome = args[0].Substring(begin, 2);
}
else
{
currentPalindrome = args[0][begin].ToString() + currentPalindrome + args[0][end].ToString();
}
Console.WriteLine(currentPalindrome);
begin--;
end++;
} while (begin >= 0 &&
begin < args[0].Length &&
end >= 0 &&
end < args[0].Length &&
args[0][begin] == args[0][end]);
}
}
}
}
}
int numOfSubPalindroms(string str){
int len = (int)str.length();
bool flag[len+1][len+1];
memset(flag, false, sizeof(flag));
int count = 0;
for(int i = len; i >= 1; i --){
for(int j = i; j <= len; j ++){
if(j == i||(j-i == 1 && str[j-1] == str[i-1]) || (flag[i+1][j-1] && str[i-1] == str[j-1])){
count++;
if(j != i)
cout << str.substr(i-1,j-i+1) << endl;
flag[i][j] = true;
}
}
}
return count;
}
Works in O(n^2) and uses additional space to reverse the string without looping over it to find if it is palindrome.
{{
public int partitionCount(String s) {
if(s == null) return 0;
else if(s.length() == 1){
return 1;
}
int count = 0;
for(int i = 0; i < s.length(); i++){
for(int j = i; j <= s.length(); j++){
if(i != j){
String sub = s.substring(i, j);
if(isPalindrome(sub)){
count++;
}
}
}
}
return count;
}
private boolean isPalindrome(String s){
return s.length() == 1 || s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());
}
}}}
Works in O(n^2) and uses additional space to reverse the string without looping over it to find if it is palindrome.
public int partitionCount(String s) {
if(s == null) return 0;
else if(s.length() == 1){
return 1;
}
int count = 0;
for(int i = 0; i < s.length(); i++){
for(int j = i; j <= s.length(); j++){
if(i != j){
String sub = s.substring(i, j);
if(isPalindrome(sub)){
count++;
}
}
}
}
return count;
}
private boolean isPalindrome(String s){
return s.length() == 1 || s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());
}
public class LookAndSaySequence {
public static void main(String args[]){
System.out.println(patternUtil(4));
}
public static String patternUtil(int input)
{
String result = "1";
while(input> 0){
input--;
char currentCharacter = result.charAt(0);
String newResult = "";
int countRipetitionChar = 0;
for(int i = 0; i< result.length(); i++) {
char nextCharacter = result.charAt(i);
if(nextCharacter != currentCharacter) {
newResult = newResult + countRipetitionChar + currentCharacter;
countRipetitionChar = 0;
currentCharacter = nextCharacter;
}
countRipetitionChar ++;
}
result = newResult + countRipetitionChar + currentCharacter;
}
return result;
}
}
-> Just keep in counting all the substrings that are palindromic, Use table to keep tack of which all substring are palindromic.
int dp(char a[],int n) {
bool table[n][n];
memset(table,0,n*n);
for(int i=0;i<n;i++) table[i][i] = true;
int count = n; // all one length are palindromic
for(int len = 2;len <= n;len++) {
for(int i=0;i<n-len+1;i++) {
int j = i+len-1;
if(j == i+1 && a[i] == a[j]) table[i][j] = true;
else {
if(a[i] == a[j]) table[i][j] = table[i+1][j-1]; //mark all palin substring
//else table[i][j] = table[i+1][j] || table[i][j-1];
}
if(table[i][j]) count++;
}
}
/*
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++)
cout<<table[i][j]<<" ";
cout<<endl;
}
*/
return count;
}
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
namespace ListOfPalindromes
{
class Program
{
static IEnumerable<string> GetListOfPalindromes(string s)
{
var listSoFar = new ConcurrentQueue<string>();
Parallel.For(0, s.Length, i => GetListOfPalindromes(s, i, 1, listSoFar));
return listSoFar;
}
private static void GetListOfPalindromes(string s, int position, int size, ConcurrentQueue<string> listSoFar)
{
if (position + size > s.Length)
return;
var ss = s.Substring(position, size);
if (IsPalindrome(ss))
listSoFar.Enqueue(ss);
GetListOfPalindromes(s, position, size + 1, listSoFar);
}
private static bool IsPalindrome(string s)
{
var length = s.Length;
if (length < 2)
return false;
for (var i = 0; i < length/2; i++)
if (s[i] != s[length - i - 1])
return false;
return true;
}
static void Main(string[] args)
{
new List<string>() {"abba", "romanesque", "malayalam", "aabbottob"}.
ForEach(s =>
GetListOfPalindromes(s).
ToList().
ForEach(p =>
Console.WriteLine($@"Palindrome for {s}: {p}")));
}
}
}
Short and sweet O(N^2) solution by finding all palindromes "anchored" at a char or a pair of chars.
void match(vector<string>& results, string s, int left, int right) {
int n = s.length();
while (left >= 0 && right < n && s[left] == s[right]) {
results.push_back(s.substr(left, right - left + 1));
left--;
right++;
}
}
vector<string> findPalindromicSubstrings(string s) {
vector<string> results;
int n = s.length();
for (int i = 0; i < n; i++) {
match(results, s, i, i + 1);
match(results, s, i, i);
}
return results;
}
-- Bruteforce:
-- check every contiguous subsequence.
-- imaging placing ( ) around each subsequence.
-- for n choices of ( there are n-1 choices of )
-- so O(n!).
--
-- Memoization:
-- if A[i..j] is a palindrome then
-- A[i-1..j+1] is if A[i-1] == A[j+1]
-- A[i-1..j] is if A[i-1] == A[j]
-- A[i..j+1] is if A[i] == A[j+1]
-- for every A[k] it's O(1) to check each possible
-- subsequence extending to either side. So it's O(n)
-- overall.
-- do this for each A[k] => O(n^2)
subpalindromes :: [Char] -> Int
subpalindromes str =
let
xs =
Vector.fromList str
n =
Vector.length xs - 1
-- construct table centered around k
-- [ 0 .. k-i..k..k+i .. n ]
-- for k-i >= 0 and k+i <= n, i <= k and i <= n-k
table k =
let
m =
min k (n-k)
eq i =
if arr Array.! (i-1) then
xs Vector.! (k-i) == xs Vector.! (k+i) ||
xs Vector.! k == xs Vector.! (k+i) ||
xs Vector.! (k-i) == xs Vector.! k
else
False
arr =
Array.array (0,m) $
(0, True) : [ (i, eq i)| i <- [1..m] ]
in
Array.elems arr
in
List.sum .
fmap (List.length . List.filter (== True) . table) $
[0..n]
void printPal(string s, int start, int end)
{
//first check whether the given string is a palindrome
if (isPalindrome(substring(s, start, end - start + 1)))
{
println(s);
}
for (int i = start; i < end; i++)
{
//recursively call this function on all splits of the given string
printPal(s, start, i);
printPal(s, i + 1, end);
}
}
Oh.. the question is to calculate the total number... you can just increment a global variable or make printPal return the total number of palindromes found so far.
for above code ::: Complexity = O(n^2 * (k))
k= average length of string i think they will be satisfied with this complexity..
i would rather go to each letter and look at its left and right till a palind is there and add them up so for abba
a = 1
b -> b, = 1
b -> b = 1
a - > a = 1
4 odd lenghts
for even length only consider if two adjacent characters are same
abba
bb - >bb, abba
2even length strings
num_palins = 6
this will be testing way less number of substrings as the total number of non-palin substring it will try is O(2n)
as it stops at first non-palin substring
in case all substrings are palin it will have same complexity as above solution
void LongestPalindromic(char *s)
{
if(!*s)
{
printf("\nNull String\n");
return;
}
int TotalPalindromes=0;
int n=strlen(s);
int i,len,maxlen,longestBegin;
bool t[30][30]={false};
for(i=0;i<n;i++)
{
t[i][i]=true;
TotalPalindromes++;
}
for(i=0;i<n-1;i++)
{
if(s[i]==s[i+1])
{
t[i][i+1]=true;
maxlen=2;
longestBegin=i;
TotalPalindromes++;
}
}
for(len=1;len<n;len++)
{
for(i=0;i<n-len;i++)
{
int j=i+len;
if(s[i]==s[j] && t[i+1][j-1])
{
t[i][j]=true;
maxlen=len;
longestBegin=i;
TotalPalindromes++;
}
}
}
printf("\nLongest Palindrome:\t");
for(i=longestBegin;i<=(longestBegin+maxlen);i++)
printf("%c",s[i]);
printf("\nTotal Number of Palindromes:\t %d\n",TotalPalindromes);
}
Solution in plain C:
#include <stdio.h>
int is_palindrome(const char *beg, const char *end)
{
while (end > beg) {
if (*end != *beg)
return 0;
beg++;
end--;
}
return 1;
}
void find_palindrome(const char *str, int pos, int last)
{
const char *beg;
const char *end;
if (pos == last)
return;
printf("P: %c\n", str[pos]);
find_palindrome(str, pos + 1, last);
beg = str + pos;
end = str + last;
while (end > beg) {
if (is_palindrome(beg, end))
printf("P: %.*s\n", end - beg + 1, beg);
end--;
}
}
void find_palindromes(const char *str)
{
find_palindrome(str, 0, strlen(str));
}
int main(void) {
find_palindromes("abba");
return 0;
}
int cntP(char[] A){
int total = 0;
int[][] B = new int[A.length+1][A.length];
for(int j = 0; j< A.length; j++){
B[0][j] = 1;
B[1][j] = 1;
total += 1;
}
for(int i = 2; i<=A.length; i++){
for(int j = 0; j<= A.length-i; j++){
if(A[j] == A[j+i-1]){
B[i][j] = A[i-2][j+1];
total += B[i][j];
} else{
B[i][j] = 0;
}
}
}
return total;
}
public int Question1(string palindrom){
int count = 0;
for (int i = 0; i < palindrom.Length; i++)
{
//int length = pallArr.Length - i;
for (int j = 1; j <= palindrom.Length - i; j++)
{
//if (pallArr[i] == pallArr[j])
string pal = palindrom.Substring(i, j);
if (IsPalindrom(pal))
{
count++;
Console.WriteLine(pal);
}
}
}
return count;
}
public bool IsPalindrom(string str) {
bool isPalindrom = true;
int startInd = 0;
int endInd = str.Length-1;
for (int i = startInd; i < endInd; i++)
{
if (str[startInd] != str[endInd])
{
isPalindrom = false;
return isPalindrom;
}
startInd++;
endInd--;
}
return isPalindrom;
}
Recursive with memoization for backtracking/pruning trees.
//
// Print all palindroms in the string
// Ex: malayalam
//
//
private static bool[,] map;
private static bool isPalindrome(string s, int l, int r)
{
int i = r;
if (r == l) {
return false;
}
if (r - l == 1) {
return true;
}
do {
if (s[l] == s[r - 1]) {
l++;
r--;
}
else {
return false;
}
} while (l < r);
return true;
}
private static void FindAllPalinDromes(string s, int l, int r)
{
if (l > r || l < 0 || r > s.Length) {
return;
}
if (map[l, r]) {
return;
}
if (isPalindrome(s, l, r)) {
Console.WriteLine("{0} @ {1},{2}", s.Substring(l, r - l), l, r - 1);
}
FindAllPalinDromes(s, l + 1, r);
FindAllPalinDromes(s, l + 1, r - 1);
FindAllPalinDromes(s, l, r - 1);
map[l, r] = true;
return;
}
public static void PrintAllPalindromes(string s)
{
int len = s.Length;
map = new bool[len + 1, len + 1];
FindAllPalinDromes(s, 0, s.Length);
}
static void Main(string[] args)
{
PrintAllPalindromes("malayalam");
}
This is O(n+p) solution where p is the number of palindromes
public static int numOfSubPalindroms(String s){
int ans = s.length();
for(int i=0; i<s.length()-1; i++){
if (s.charAt(i)==s.charAt(i+1)){
ans += 1 + numberOfExpansions(s,i,i+1);
}
}
for(int i=0; i<s.length()-2; i++){
if (s.charAt(i)==s.charAt(i+2)){
ans += 1 + numberOfExpansions(s,i,i+2);
}
}
return ans;
}
private static int numberOfExpansions(String s, int left, int right){
int ans = 0;
for (int i=1; left-i>=0 && right+i<s.length(); i++){
if (s.charAt(left-i)==s.charAt(right+i)){
ans++;
} else {
return ans;
}
}
return ans;
}
Agree to Joe kidd, should use dynamic programming.
Java code:
public static int numOfPalin(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int count = 0;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (j - i < 2 && s.charAt(i) == s.charAt(j))
dp[i][j] = true;
if (i < s.length() - 1 && j > 0
&& dp[i + 1][j - 1]
&& s.charAt(i) == s.charAt(j))
dp[i][j] = true;
if (dp[i][j]) {
count++;
}
}
}
return count;
}
The solution to this problem may base on the dynamic programming approach to palindrom finding (google it, as there is plenty of implementation). Then when we have a table P[i][j] and it's value is greater than zero, we know the value between i and j in the original string is a palindrom, so we may print it. The solution would be O(n^2).
- joe kidd November 04, 2013