CareerCup

Must we break it into the minimum number of palindromes? That sounds challenging.

@eugene- I think that is what it is. Then the problem would be finding longest palindromes and covering all characters in the string. Can be done using a suffix tree with minimum complexity

@akashj

your code would fail in case of string "abaab"..
ur ans aba | a | b

whereas ans should be a | baab

Algo.
1. find the longest palindrome in string.
2. repeat the procedure for remaining two strings (left and right side of palindrome).

This is a shortest path problem. Find all substring(a,b) (from a to b-1) that are palindromes. Then there is an edge from a to b. Need to find the shortest path from 0 to S.size().

void solve(string S) {
		int N = S.size();
		vector<vector<int> > to(N+1);
		for(int i=0; i < N; i++) for (int j=i+1;j <=N; j++) {
			int len = j -i;
			string sub = S.substr(i,len);
			bool ok = true;
			for(int k = 0; k < len/2;k++)
				if (sub[k] != sub[len-1-k])
					ok = false;
			if (ok)
				to[i].push_back(j);
		}
		vector<int>prev(N+1,-1);
		queue<int> Q;
		Q.push(0);
		while (!Q.empty()) {
			int curr =Q.front();
			Q.pop();
			vector<int> next = to[curr];
			for(int i =0; i < next.size(); i++) if (prev[next[i]] < 0) {
				Q.push(next[i]);
				prev[next[i]] = curr;
			}
		}
		vector<int> path;
		int end = N;
		do {
			path.insert(path.begin(), end);
			end = prev[end];
		}	while (end >=0);
		for (int i =0; i < path.size()-1; i++) {
			string sub = S.substr(path[i],path[i+1]-path[i]);
			cout << sub << " ";
		}
		cout << endl;
	}

The more I think over this problem, the more interesting it seems to be.

We know we can find the longest palindrome of a string using DP at O(N);

Then I thought

1) Use greedy algorithm to find the longest palindrome
2) Update the string and repeat step 1)

This worked in many cases.

However, given input s= aabab

it may output a aba b, or aa bab.

Obviously, if the question is to separate the string into minimal number of palindromes, then the greedy algorithm will fail.

and this problem may indeed be very difficult

why cant we use string indexof,lastIndexOf and output values between the two indexes

void allPalindroms(char *str)
{
     int len = strlen(str);
     if(len != 0)
     {
            int i, j = --len;
            for(i = 0; i < j; i++,j--)
            {
                  if(str[i] != str[j])
                  {
                       i = -1;
                       len = j -1;
                  }
            }
             for(i = 0; i <= len; i++)
                   printf("%c",str[i]);
              printf("\n");
              allPalindroms(str + len + 1);     
     }                  
}
void main()
{
        allPalindroms("aabbbccdeef");
}