CODEWITHSUNDEEP
javastringalgorithmoptimizationpalindrome
batman
batman

Reputation: 3685

How to convert a given string to palindrome?

I had an interview question which is:

"Convert a given string to an palindrome, provided the output (palindrome string) should contain the substring of the given string"

So I did this way, given root as input I will find the reverse of that string and append it to the given input. So I get string :

roottoor

which is an palindrome and also contains i/p (root) is present in the o/p.

Given the solution, the interviwer said, its not optimal solution can you give an optimal one?

I couldn't able to find any apart from this.

Any other solutions?

He said its need to be done in Java.

Upvotes: 0

Views: 910

Answers (2)

Erich Kitzmueller
Erich Kitzmueller

Reputation: 36977

For a given string s, find the longest substring s1 at the end of s that is already a palindrome. Then just put the reverse of s\s1 at the end.

For example, for the input string "lambada", "ada" is a palindrome, so you just add the reverse of "lamb" and the result is "lambadabmal".

EDIT: Considering maartinus' answer, you should also check the opposite direction and choose the one that results in a shorter palindrome:

For a given string s, find the longest substring s1 at the beginning of s that is already a palindrome. Then just insert the reverse of s\s1 at the beginning.

For example, for the input string "arafat", "ara" is a palindrome, so you just insert the reverse of "fat" at the beginning and the result is "tafarafat".

Upvotes: 5

maaartinus
maaartinus

Reputation: 46392

The other answer obviously misses to look at the beginning. Example

racecars -> racecarsracecar // when only the end is considered

racecars -> sracecars       // when the start is considered

Just look at both ends and return the better result.

Upvotes: 3

Related Questions