Add the least amount of characters to make a palindrome

algorithm palindrome
Waley Chen picture Waley Chen · Sep 11, 2013 · Viewed 14.3k times · Source

The question:

Given any string, add the least amount of characters possible to make it a palindrome in linear time.

I'm only able to come up with a O(N2) solution.

Can someone help me with an O(N) solution?

Answer

Chronial picture Chronial · Sep 11, 2013
  1. Revert the string
  2. Use a modified Knuth-Morris-Pratt to find the latest match (simplest modification would be to just append the original string to the reverted string and ignore matches after len(string).
  3. Append the unmatched rest of the reverted string to the original.

1 and 3 are obviously linear and 2 is linear beacause Knuth-Morris-Pratt is.

Related questions

Write a function that returns the longest palindrome in a given string

e.g "ccddcc" in the string "abaccddccefe" I thought of a solution but it runs in O(n^2) time Algo 1: Steps: Its a brute force method Have 2 for loops for i = 1 to i less than array.length -1 for j=…

Read More
Find all substrings that are palindromes

If the input is 'abba' then the possible palindromes are a, b, b, a, bb, abba. I understand that determining if string is palindrome is easy. It would be like: public static boolean isPalindrome(String str) { int len = str.length(); …

Read More
how to find longest palindromic subsequence?

Here is the problem (6.7 ch6 ) from Algorithms book (by Vazirani) that slightly differs from the classical problem that finding longest palindrome. How can I solve this problem ? A subsequence is palindromic if it is the same whether read left to …

Read More