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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Build a Palindrome
  5. Discussions

Build a Palindrome

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 44 Discussions, By:

votes

Please Login in order to post a comment

  • kirill_frolov77
    6 years ago+ 1 comment

    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...

    8|
    Permalink
  • barat_gabor
    3 years ago+ 1 comment

    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.

    5|
    Permalink
  • ivan_soroko
    5 years ago+ 1 comment

    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.

    3|
    Permalink
  • lukerucks
    6 years ago+ 1 comment

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

    3|
    Permalink
  • b_vsbrk
    5 years ago+ 1 comment

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

    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature