Hey guys, I think the easiest (and the most logical) approach would be to use suffix trees. This problem is naturally reduced to "longest common substring" problem if you reverse the second string. There is time- and space-efficient O(n + m) solution for that, using Ukkunen's algorithm. But unfortunately the algorithm is quite complex.

Based on the length of input (~10^5), no O(n^2) algorithm will work here. Maybe O(n*log(n)) will still do...

I can confirm what others said earlier: no naive, quadratic time complexity solution will work. :) It gives you 40-50% success rate; a bit higher if you do some hacks, like ignoring very short matches if the strings are long. Rest will time out.

Also, no trickery with constructing the result from the longest common reversed substring + longest palindrome will work, because these constituent lengths of the longest solution differ/overlap in all possible ways. So, it seems you do need to try all combinations, by using an underlying linear time search algorithm.

This means it comes down to building a suffix tree algorithm based on someone else's work (e.g. Ukkonen, Farach), instead of writing your own solution from scratch (unless you're a genius who can do better than people who've worked in this area for years).

One good thing is that even that won't be a trivial plug-in solution, so if you solve this problem, it will actually mean something. Probably that's why the solve rate is so low.

In order to solve this use 2 structures: 1) Palindromic Tree 2) Suffix Tree

For every index in the first string find longest palindrome that starts at this index and longest common substring that ends at this index. Repeat this logic for the second string. Of course you need to reverse one of them in both steps. Remember that there can be multiple answers with the same length.

Is it possible to do this in less than O(N^2)? No matter how I optimize my Python solutions, I'm timing out...

As given from the question if the two strings are bac and bac then answer is aba. Why not bab ?