### Algorithm Challenge

I promise this is not an assignment, I found the question on a site and I am curious to see what people on this site come up with.

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

Go crazy!
closed account (Dy7SLyTq)
hmmm... thats a good one, but correct me if im wrong it doesnt seem too difficult

edit: does it have to be a real word?
Last edited on
yes, I guess I should have given example:

ex input/output:
 ```in: jeej out: jeej in:jeefgeej out:jeegfgeej in:a out:a in:ppalind out:dnilappalind```
Last edited on
I think some kind of similarity finder is needed to choose where the possible "middle" of the palindrome may be. After you locate the middle, you add the missing characters.

 correct me if im wrong it doesnt seem too difficult

I won't even dare open the editor until I see more members post better ideas.
closed account (S6k9GNh0)
This could be done algorithmically off the top of my head.

1. Make the string a palindrome. Easiest way to do this is to print a string the string in reverse order from the front or the back of the string. This is also the largest way to make the word a palindrome.

2. Take away characters in pairs from the middle towards the ends. If it doesn't take away the original word and it doesn't remove it from being a palindrome, then at the end, you'll have a reduced palindrome.

So...

jeej
jeejjeej
jeeeej
jeej

You're left with the original characters and smallest palindrome.

ppalind
ppalinddnilapp
palinddnilap

I haven't tested this and its 3AM... so use at your own risk.
Last edited on
jeefgeej
so
jeefgeejjeegfeej

I don't think you can get the below from that by removing center pairs...or any pairs for that matter.
jeegfgeej

I don't think your method works for anything other then strings that are already palindromes or have cannot be made into them besides adding a copy to end basically.
This is very easy.

1. Find the largest suffix that is a palindrome.
2. Append the reversed prefix (left after cutting off the suffix found in step 1.) to the end of the word.

 ``1234`` ``````def isPalindrome(s: String) = s.reverse == s def makePalindrome(s: String) = s + s.take((0 to s.length).find(i => isPalindrome(s.substring(i))).get).reverse ``````

 ``123456789101112131415161718192021222324`` ``````scala> makePalindrome("") res13: String = "" scala> makePalindrome("a") res14: String = a scala> makePalindrome("ab") res15: String = aba scala> makePalindrome("abc") res16: String = abcba scala> makePalindrome("abcd") res17: String = abcdcba scala> makePalindrome("aaa") res18: String = aaa scala> makePalindrome("aba") res19: String = aba scala> makePalindrome("abcb") res20: String = abcba ``````
Last edited on
 ```makePalindrome("noob")=="nooboon", len==7 #expected: len==6, "nboobn" or "bnoonb"```

Dot-plots are fun, but would they help?
 ``` jeefj j. . e .. e .. f . j. .```

Insert 'f' =>
 ``` jfeefj j. . f . . e .. e .. f . . j. .```

All right, the original challenge stated **add** and I misread it as "append". My code works only for appending. If you can prepend, insert and append, then this is a whole different story.
I love a challenge me.
An idea following from the dot-plot: Needleman-Wunsch algorithm, but this time an alignment of string with its reverse. Then fill the gaps.
Last edited on
One idea perhaps can be:

We know that the upperbound of the answer is the length of string itself.

Say the original string is abcdeba

We check character-wise ( S[i] == S[length-i-1] ), when we get a false condition ('c' != 'e'), then we have two options:
-> add c to where e was, or add e to where c was.
We will have to evaluate both options and maybe do this recursively and pick out method with least number of character additions.
The OP said to "add". Not "change". In the case of "abcdeba", you would have to add two characters. Order doesn't matter so long as the palindrome holds:

abcedecba
abecdceba

 BTW: "ppaba"
Last edited on
Yes I meant to insert only, not replace. Sorry it wasn't clear.

EDIT: for ppaba,

Iteration 1: appaba or ppabap
2: abppaba or appabpa or papabap or ppabapp

ppabapp is a paindrome so we stop. Answer is 2.

However, the memory required for this algorithm increases exponentially as the length of string increases.

EDIT 2: The algorithm may be improved if instead of just one letter, we check for the next one and (the next one if needed) as well to rule out the other options.
Last edited on
Funny all the answers on StackOverflow assume the goal is to append only, and insertions are not allowed. So they won't handle the "noob" case properly.

Ok, so here is the code:

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576`` ``````def makePalindrome(str: String): String = { def paretoMin(points: Iterable[(Int, Int)]): List[(Int, Int)] = { val sorted = points.toSeq.sortBy(identity) (List.empty[(Int, Int)] /: sorted) { (result, e) => if (result.isEmpty || e._2 <= result.head._2) e :: result else result } } /** Find all pairs directly nested within a given pair. * For performance reasons tries to not include suboptimal pairs (pairs nested in any of the pairs also in the result) * although it wouldn't break anything as prune takes care of this. */ def pairs(left: Int, right: Int): Iterable[(Int, Int)] = { val builder = List.newBuilder[(Int, Int)] var rightMax = str.length for (i <- left until (str.length - right)) { rightMax = math.min(str.length - left, rightMax) val subPairs = for (j <- right until rightMax if str(i) == str(str.length - j - 1)) yield (i, j) subPairs.headOption match { case Some((a, b)) => rightMax = b; builder += ((a, b)) case None => } } builder.result() } /** Builds sequences of size n+1 from sequence of size n */ def extend(path: List[(Int, Int)]): Iterable[List[(Int, Int)]] = for (p <- pairs(path.head._1 + 1, path.head._2 + 1)) yield p :: path /** Whether full or degenerated. Full-pairs save us 2 characters, degenerated save us only 1. */ def isFullPair(pair: (Int, Int)) = pair._1 + pair._2 < str.length - 1 /** Removes pareto-suboptimal sequences */ def prune(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = { val allowedHeads = paretoMin(sequences.map(_.head)).toSet val containsFullPair = allowedHeads.exists(isFullPair) sequences.filter(s => allowedHeads.contains(s.head) && (isFullPair(s.head) || !containsFullPair)) } /** Dynamic-Programming step */ @tailrec def search(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = { val nextStage = prune(sequences.flatMap(extend)) nextStage match { case List() => sequences case x => search(nextStage) } } /** Converts a sequence of nested pairs to a palindrome */ def sequenceToString(sequence: List[(Int, Int)]): String = { val lStr = str val rStr = str.reverse val half = (for (List(start, end) <- sequence.reverse.sliding(2)) yield lStr.substring(start._1 + 1, end._1) + rStr.substring(start._2 + 1, end._2) + lStr(end._1)).mkString if (isFullPair(sequence.head)) half + half.reverse else half + half.reverse.substring(1) } sequenceToString(search(List(List((-1, -1)))).head) } ``````

Testing:
 ``1234567891011`` ``````scala> makePalindrome("noob") res1: String = nboobn scala> makePalindrome("ann") res2: String = anna scala> makePalindrome("aaa") res3: String = aaa scala> makePalindrome("123456789875432") res4: String = 12345678987654321``````

For a 40-character word, the timing is below 0.5 ms, although the algorithm itself is pretty sloppy. There is a lot of room for improving performance of pairs and paretoMin.
Last edited on
nice
Topic archived. No new replies allowed.