CareerCup

This problem can be solved by longest palindrome substring which is solved by dynamic programming in O(N^2).

Problem Analysis:
1. Given a substring P[i,i], P[i,i] is always a palindrome. // Base case #1
2. Given a substring P[i,i], P[i,i+1] is palindrome if a_i = a_i+1, hence...
3. We can observe that for a given substring P[i,j], P[i,j] is a palindrome if P[i+1,j-1] is a palindrome and a_i = a_j.
4. There are O(n^2) substring from a string of length N as all alphabets must be consecutive (substring does not follow a O(2^N) subset). To check if a substring is palindrome it take O(k) where k is the size of substring. Hence, find the longest substring take O(N^3).

Solution:
Base on these assumption, #3 we can reduce the isPalindrome(String str) from O(k) down to O(1). This will yield a O(N^2) solution.

1. First build a table of size NxN
2. Fill in a diagonal cells with base case #1
3. For each P[i,i+1] do Base case #2
4. For a substring of size 3 to N and starting from a_0 to a_N-k do #3.

For(int k=3; k<N, k++)
	For(int i=0;i<= N-k;i++){
		if(P[i+1,j-1] && a_i == a_j)  P[i,j] = k;
		else P[i,j] = 0;
        }

Then the table P will be done. The last step is to print all cell in P. We can observe that the cell P[i,j] represent a substring(i,j). If this cell is not zero then it will be the size of palindrome substring. Print all P[i,j] != 0.

I did it using memoization but I think it can be done by DP. Below is the code with some helping routines. I hope the code is self explanatory.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int checkPalindrom (char* pStr, int start, int end)
{
	int i=start, j=end;
	while(i<j)
	{
		if(pStr[i] != pStr[j])
			return 0;
		i++;
		j--;
	}
	return 1;
}
void printPalindrom(char* pStr, int start, int end, char pMemoizationMatrix[][100])
{
	if(start<end)
	{
		if(pMemoizationMatrix[start][end]=='#')
		{
			pMemoizationMatrix[start][end]=checkPalindrom(pStr,start,end)+'0';
			printPalindrom(pStr, start+1,end,pMemoizationMatrix);
			printPalindrom(pStr,start,end-1,pMemoizationMatrix);
		}
	}
}
void printAllPalindrom(char* pStr)
{
	int len = strlen(pStr);
	int i,j;
	char temp, *pTemp;
	char ppStrMatrix[100][100];
	for(i=0;i<len;i++)
	{
		for(j=0;j<len;j++)
		{
			ppStrMatrix[i][j]='#';
		}
	}
	printPalindrom(pStr,0,len-1,ppStrMatrix);
	for(i=0;i<len;i++)
	{
		for(j=0;j<len;j++)
		{
			if(ppStrMatrix[i][j]=='1')
			{
				temp=pStr[j+1];
				pStr[j+1]=0;
				pTemp=&pStr[i];
				printf("%s\n", pTemp);
				pStr[j+1]=temp;
			}
		}
	}	
}
int main()
{
	char* pString=0;
	int len=0;
	int numOfBytes=0;
	len=getline(&pString,&numOfBytes,stdin);
	pString[len-1]=0;
	printAllPalindrom(pString);
	return 0;
}

Keep Hash where Key is last index of found palindrome(s) and Values are start index(es) of these palindrome(s).
Then scan original string and for i-th character check:
- if s[i]==s[i-1] - add to hash [i:i-1]
- if s[i]==s[i-2] - add to hash [i:i-2]
- if hash contains palindromes with Key=i-1, then for each value j do:
if s[j-1]==s[i] then add to hash [i,j-1]

The algorithm looks effective, but still O(n^2) time and O(n^2) memory as there are potentially O(n^2) palindromes.

void printAllPalindromes(char* str) {
  if(strlen(str) == 1) {
    return;
  }
  else if(strlen(str) == 2 && str[0] == str[1]) {
    printf("%s\n", str);
    return;
  }
  int a = 0, b = 1, c = 2;
  while(str[b] != '\0') {
    if(str[a] == str[b]) {
      int temp1 = a, temp2 = b;
      while(temp1 >= 0 && str[temp2] != '\0') {
        if(str[temp1] == str[temp2]) {
          temp1--;
          temp2++;
        }
        else
          printStr(str, temp1, temp2) // prints the string starting index temp1 till temp2
      }
    }
    if(str[c] == str[a]) {
      int temp1 = a, temp2 = c;
      while(temp1 >= 0 && str[temp2] != '\0') {
        if(str[temp1] == str[temp2]) {
          temp1--;
          temp2++;
        }
        else
          printStr(str, temp1, temp2) // prints the string starting index temp1 till temp2
      }
    }
    ++a;
    ++b;
    ++c;
  }
}

This algorithm requires no extra space. The time complexity depends on the number of palindromes I think. For e.g., if there are no palindromes, it would take O(n) to finish. But if the string just contains one character like "aaaaaaaa", it would take O(N^2).

Please comment if you think that the algorithm won't work

//get all the palindromes whose central is at centerPos
List<String> getPalindromes(String str, int centerPos)
{
List<String> list = new ArrayList<String>();
int len = str.length();
for (int i = 1; centerPos - i >= 0 && centerPos + i < len; i ++)
{
if (str.charAt(centerPos - i) == str.charAt(centerPos + i))
{
list.add(str.substring(centerPos - i, centerPos + i + 1));
}
else
{
break;
}
}

for (int i = 0; centerPos - i >= 0 && centerPos + 1 + i < len; i ++)
{
if (str.charAt(centerPos - i) == str.charAt(centerPos + 1 + i))
{
list.add(str.substring(centerPos - i, centerPos + i + 2));
}
else
{
break;
}
}
return list;
}

void printAllPalindromes(String str)
{
for (int i = 0; i < str.length() - 1; i ++)
{
List<String> list = getPalindromes(str, i);

for (String pal: list)
{
System.out.println(pal);
}
}
}

It is in O(n^2), but the average should be in O(n).

<pre lang="" line="1" title="CodeMonkey97694" class="run-this">void printChar(char *start, char *end)
{
if (NULL == start || NULL == end)
return;

char *pstr = start;
while (pstr <= end)
{
printf("%c",*pstr++);
}
printf("\n");
}

int printPalindromeStr(char* str)
{
if (NULL == str || 0 == *str)
return -1;

char *pStr = str;
char *pStrEnd = str+strlen(str);
pStr++;
pStrEnd--;
char *pleft, *pright;
while (pStr < pStrEnd)
{
pleft = pStr-1;
pright = pStr+1;
while (pleft >= str && pright <= pStrEnd && *pleft == *pright)
{
printChar(pleft,pright);
pleft--;
pright++;
}

pleft = pStr-1;
pright = pStr;
while (pleft >= str && pright <= pStrEnd && *pleft == *pright)
{
printChar(pleft,pright);
pleft--;
pright++;
}

pleft = pStr;
pright = pStr+1;
while (pleft >= str && pright <= pStrEnd && *pleft == *pright)
{
printChar(pleft,pright);
pleft--;
pright++;
}
pStr++;
}
return 0;
}
</pre><pre title="CodeMonkey97694" input="yes">
</pre>

Accordinfg the me the simplest approch to do this is as follows.
1. Store the elements from backwards in an array.
2. Now take the two arrays(original one , and the one explained above and find out all the common substring in both of them. This gives all the palindromes.

It can be done by a modification in longest common subsequence method.

/**
	 * Time: O(n)
	 * Space: O(1)
	 */
	private List<String> findPalindroms(String str){
		
		List<String> allPalindroms = new LinkedList<String>();
		
		final char[] arr = str.toCharArray();		
		StringBuilder palindrome = new StringBuilder();
		
		for( int i = 0; i < arr.length-1; i++ ){
			
			if( arr[i+1] == arr[i] ){
				
				palindrome.setLength(0);
				palindrome.append(arr[i]);
				
				for( int j = i+1; j < arr.length && arr[i] == arr[j]; j++ ){
					palindrome.append(arr[j]);					
					allPalindroms.add( palindrome.toString() );
				}
			}		
			else if( i > 0 && arr[i-1] == arr[i+1] ){
				
				int left = i-1;
				int right = i+1;
				
				palindrome.setLength(0);
				palindrome.append(arr[i]);
				
				while( left >= 0 && right < arr.length && arr[left] == arr[right] ){
					palindrome.insert(0, arr[left]).append(arr[right]); 
					allPalindroms.add(palindrome.toString());					
					--left;
					++right;
				}		
			}
		}
		
		return allPalindroms;
	}

This can be done in O(n) using suffix trees. Basically create a common suffix tree from the string and the reverse of the string and then print all the branches that have endings from both the tree.

printpal(char *s, int min, int max)
{
int i = 0;
// check if it is a palindrome or not.
if(s[min+i]!=s[max-i])
return 0;

// print the palindrome
printf("\n");
for(i = min; i<=max; i++)
printf("%c",s[i]);
return 1;

}


main()
{
int i = 0,l,min,max;
char s[] = "ababbab";

int len = strlen(s);
float mid;

for (mid = 0.0; mid <= len-1; mid += 0.5)
{
for (l = 0; 1 ; l++)
{
min = (int)floor(mid-l);
max = (int)ceil(mid + l);
if(min < 0 || max >= len)
break;

if(min < max)
if(!printpal(s,min,max))
break; // break because now no string with same mid point and of more length can be a palindrome.
}
}
return;
}

<pre lang="" line="1" title="CodeMonkey17694" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);

for(int i=1;i<s.length()-1;i++)
{
for(int j=i-1,k=i+1;(j>=0)&&(k<s.length());j--,k++)
{
if(s.charAt(i)==s.charAt(k))
{
System.out.print(s.charAt(i));

System.out.print(s.charAt(k));

System.out.println("\n");
for(int l=i-1,m=k+1;l>=0&&m<s.length();l--,m++)
if(s.charAt(l)== s.charAt(m))
for(int f=l;f<=m;f++)
System.out.print(s.charAt(f));
System.out.println("\n");

}
if(s.charAt(j)==s.charAt(k))
{
for(int p=j;p<=k;p++)
System.out.print(s.charAt(p));
System.out.println("\n");

}
else break;

}
}

}
}

</pre><pre title="CodeMonkey17694" input="yes">adgssgdhjabbac</pre>

using namespace std;

const int MaxNum=200;
int P[MaxNum][MaxNum];

int main()
{

freopen("in.txt", "r", stdin);
string m_str;
int i,j,Offset;
while(cin>>m_str)
{
	int CharNum=m_str.size();
	memset(P,0,sizeof(P));
	for(i=0;i<CharNum-1;i++)
	{
		P[i][i]=1;
		if (m_str[i]==m_str[i+1])
		{
			P[i][i+1]=2;
		}
	}
	P[CharNum-1][CharNum-1]=1;

	for(Offset=2;Offset<CharNum;Offset++)
	{
		for(i=0;i<CharNum-Offset;i++)
		{
			j=i+Offset;
			if (P[i+1][j-1]>0&&m_str[i]==m_str[j])
			{
				P[i][j]=Offset;
				
			}
		}
	}
	for(i=0;i<CharNum;i++)
	{
		for(j=i+1;j<CharNum;j++)
	
		{
			if(P[i][j]>0)
				cout<<m_str.substr(i,j-i+1)<<" ";

		}
		
	}
	
}


}

vector<string> findPalsFrom(const string& fwd, const string& rev, size_t pos)
{
    size_t c = 2;
    size_t rpos = rev.size() - pos - 1;
    vector<string> ret;
    while ((pos + c - 1) < fwd.size() && (rpos + c - 1) < rev.size()) {
        string lstr1(fwd, pos, c);
        string lstr2(fwd, pos + 1, c);
        string rstr(rev, rpos, c);
        if (lstr1 == rstr) {
            ret.push_back(fwd.substr(pos - (c - 1), (2 * c) - 1));
        } else if (lstr2 == rstr) {
            ret.push_back(fwd.substr(pos - (c - 1), (2 * c)));
        } else {
            return ret;
        }
        c += 1;
    }

    return ret;
}

vector<string> pals(const string& s)
{
    string rev(s);
    reverse(rev.begin(), rev.end());
    vector<string> ret;
    for (size_t i = 1; i < s.size() - 1; i++) {
        vector<string> v = findPalsFrom(s, rev, i);
        ret.insert(ret.end(), v.begin(), v.end());
    }

    return ret;
}

int main()
{
    string s("abbacabdadba");
    vector<string> palindromes = pals(s);
    std::copy(palindromes.begin(), palindromes.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

    return 0;
}

This is a fairly simple approach. Reverse the string and compare it to the original, piece by piece. This is an O(n^2) algorithm but it will never actually run in n^2 time.

A smarter algorithm would recognize sub-palindromes while looking at bigger palindromes (e.g. abbadabba is a palindrome but so is abba and abba) ,which could come much closer to an O(n) algorithm but there's no way I could write something like that in a 45 minutes interview :)

int strpalin(){
	char str[20];
	char tstr[10];
	int i,j,k,m,n;
	strcpy(str,"abbcacbca");
	n = strlen(str);
	for(i=1;i<n;i++){
		if(str[i] == str[i+1]){
			printf("%c%c\n",str[i],str[i+1]);
		}
		j = 1; k = 1;
		while(j >=0 ) {
			if(str[i-k] == str[i+k]) {
				for(m=i-k;m<=(i+k);m++) printf("%c",str[m]); printf("\n");
				k++;
				j = i - k;
			}
			else break;
		}
	}
	return 0;

}

test

I believe the best response is to search palindromes which are centered in each character of string str.
The brute force aproach would chech if every substring is a palindrome. To build all substrings it would be n^2, and to check if then are palindromes is n (worst case). Hence if would be n^3.
If you check for all palindroms wich are centered in each caracter, you would spend O(n+p), n being the number of characters and p being the numbers of palindromes. I dont believe there is a way to find all palindromes without the p part(you cant find a palindrome without search for it), and n is the part where you search for the palindromes. Even the worst case for string "aaaaaaaaaaa", fits this analysis. Is is not that the Time is n^2, is that there are really n^2 palindromes (a lot repeated), but well, they are there in different places.

I wrote a code that does this.
1. function Set<String> findPalindrome(...) iterates through each char looking for palindromes. For each char i, the even palindromes will start at i and i+1 (could be i-1 and i, doesnt matter), and odd ones will start at i-1 and i+1.
2. function void findPalindrome(...) tries to find palindromes that starts at lower and ends at upper. if char[lower] == char[upper] we have a palindrom between that indexes, otherwise makes no sense searching anymore.

public static Set<String> findPalindrome(String str) {
		Set<String> found = new LinkedHashSet<String>();
		for (int i=0; i<str.length();++i) {
			findPalindrome(found, str, i, i+1); // even letters
			findPalindrome(found, str, i-1, i+1); // odd letters
		}
		return found;
	}
	private static void findPalindrome(Set<String> found, String str, int lower, 
		int upper) {
		while (lower >=0 && upper < str.length()) {
			if (str.charAt(lower) != str.charAt(upper))
				return;
			found.add(str.substring(lower, upper+1));
			--lower;
			++upper;
		}
	}

Using Dynamic Programing
m[i][j] meas s[i..j] is palindrome
1. m[j-1][j] = 1, if s[j] = s[j-1]
2. m[j-2][j] = 1, if s[j] = s[j-2]
3. m[k][j] = 1(k < j-2), if m[k+1][j-1] && s[k] == s[j]

Time O(n*n), Space O(n*n);
void solve()
{
string s1 = "abbcacbca";
int m[MAX_SIZE][MAX_SIZE];
memset(m, 0, sizeof(m));

int i = 0, j = 0;
for(i = 1; i < s1.size(); i++)
{
if(s1[i] == s1[i-1])
{
m[i-1][i] = 1;
print(s1, i-1, i);
}
else if((i-2 >= 0) && (s1[i] == s1[i-2]))
{
m[i-2][i] = 1;
print(s1, i-2, i);
}

for(j=i-2; j>=0; j --)
{
if(!m[j][i-1]) continue;
if((j>=1) && (s1[j-1] == s1[i]))
{
if(!m[j][i])
{
m[j][i]= 1;
print(s1, j-1, i);
}
}
}
}
for(i=0; i<s1.size(); i++)
{
for(j=0; j<s1.size(); j++)
cout<<m[i][j]<<" ";
cout<<endl;
}
}

every time choose the center char; then expand to left and right.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

vector<string> palindrome(char* array, int n)
{
    vector<string> result;
    for (int i = 1; i < n - 1; ++i)
    {
        int offset = 1;
        while (i - offset >= 0 && i + offset < n && array[i - offset] == array[i + offset])
        {
            result.push_back(string(&array[i - offset], 1 + (offset << 1)));
            ++offset;
        }
    }
    for (int i = 1; i < n  - 1; ++i)
    {
        int offset = 0;
        while (i - offset >= 0 && i + offset + 1 < n && array[i - offset] == array[i + offset + 1])
        {
            result.push_back(string(&array[i - offset], 2 + (offset << 1)));
            ++offset;
        }
    }
    return result;
}

int main()
{
    char array[1000];
    cin >> array;
    vector<string> result = palindrome(array, strlen(array));
    vector<string>::iterator iter;
    for (iter = result.begin(); iter != result.end(); ++iter)
    {
        cout << *iter << endl;
    }
    return 0;
}

I am using a DP to solve this problem. This should work.

public static void main(String[] args) {
        String input = "abccba";
        int length = input.length();
        int[][] matrix = new int[length][length];
        for(int i = 0; i < length; i++){
            for (int j = 0; j < length; j++){
                if(i > j){
                    matrix[i][j] = 0;
                }
                if (i == j){
                    matrix[i][j] = 1;
                }
            }
        }
        for(int size = 2; size < length+1; size++){
            for (int i = 0; i < length+1 - size; i++){
                int j = i + size - 1;
                // if size of subarray is 1
                int matrixValue = -1;
                if(size == 1)
                    matrixValue = 1;
                else if (size <= 3){
                    if (input.charAt(i) == input.charAt(j)){
                        matrixValue = 1;
                    }
                    else
                        matrixValue = 0;
                }
                else {
                    // if size of subarray > 3
                    if(matrix[i+1][j-1] == 0)
                        matrixValue = 0;
                    else if(matrix[i+1][j-1] == 1){
                        if(input.charAt(i) == input.charAt(j))
                            matrixValue = 1;
                        else
                            matrixValue = 0;
                    }
                    else if ((matrix[i][j-1] == 1) || (matrix[i+1][j] == 1)){
                        if((input.charAt(i) == input.charAt(j) && (matrix[i+1][j-1] == 1))){
                            matrixValue = 1;
                        }
                        else
                            matrixValue = 0;
                    }
                }
                matrix[i][j] = matrixValue;
            }
        }


        for(int i = 0; i < length; i++){
            for (int j = 0; j < length; j++){
                if(i > j || i == j)
                    continue;
                else
                if(matrix[i][j] == 1){
                    System.out.println(input.substring(i,j+1));
                }
            }
        }


    }