CareerCup

You'd have to be careful to maintain a state variable indicating which part of the string you're currently matching and to return false if you ever see an unexpected state. You wouldn't want something like XXXXBBBXXXCX to match.

How do you know what is p's end and Z's start??

my understanding is "keep pushing and keep trace of positions of first character of the string in the stack" may be this is complication but what if i maintain a stack as well as a queue and then compare at the end by poping from stack and dequeing from queue>

I assume the answer's no. Otherwise, we claim that p = "" and q = "" and we return true. So the approach of keeping a stack and then keeping track of which section of the string we're on is probably the proper approach.

Probably. The problem does become interesting if we want to minimize the length of z.

Is it that interesting? We're going to have to buffer characters anyway so that we can match a sequence of characters to the sequence in reverse, so once we've buffered the characters into an array that we have random access to, it's just scanning from both the front and back for the max sequence. It's a little more interesting if we don't have enough space to do that and have to make multiple passes, but it's still not all that exciting.

Not _that_ interesting, but slightly more than the original problem.

Try doing it in one pass with sub-linear space (i.e an online algorithm, which do tend to be interesting). Perhaps that will make it interesting to you. Of course, I don't know if a solution exists, but I do know that palindrome detection has some surprising online algorithms. You might want to search the web for those.

And to be honest, I was actually thinking of the problem where pq is a palindrome and length of p need not be the same as length of q, when I wrote that.