We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Build a Palindrome
You are viewing a single comment's thread. Return to all comments →
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.