Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Find Shortest Palindrome Possible (Main Thread)

Here is the interview question prompt, presented for reference.

We have a string str like the following:

const str = "bubble";

Find a way to convert it to a palindrome by inserting characters in front of it. Recall that a palindrome is defined as "a word, phrase, or sequence that reads the same backward as forward".

What's the shortest palindrome that can be returned? For example, the following above string should return:

shortestPalindrome("bubble")
// "elbbubble"

Constraints

  • Length of the given string <= 1000
  • The string can contain any ASCII letters
  • Expected time complexity : O(n)
  • Expected space complexity : O(1)

You can see the full challenge with visuals at this link.

Challenges • Asked over 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Find Shortest Palindrome Possible.

Ben Commented on Feb 20, 2022:

The question said:
> Expected time complexity : O(n)

but the solution said:
> The time complexity is O(n2)

I believe the question is incorrect.