## Making A Palindrome

### September 29, 2015

Our algorithm works in two passes: First, run through the input accumulating frequency counts of each character. Second, generate the palindrome, or indicate that it is not possible to do so if more than one character occurs an odd number of times; since the problem didn’t specify, we order the characters of the string in increasing order before the center and decreasing order after it:

```(define (palin str)
(define (string-reverse str) (list->string (reverse (string->list str))))
(let ((freqs (make-vector 256 0)))
(define (s t i d)
(string-append t
(make-string (/ (vector-ref freqs i) d) (integer->char i))))
(do ((cs (string->list str) (cdr cs))) ((null? cs))
(let ((i (char->integer (car cs))))
(vector-set! freqs i (+ (vector-ref freqs i) 1))))
(let loop ((i 0) (left "") (center ""))
(cond ((= 256 i) (string-append left center (string-reverse left)))
((even? (vector-ref freqs i)) (loop (+ i 1) (s left i 2) center))
((string=? center "") (loop (+ i 1) left (s center i 1)))
(else #f)))))

> (palin "pprrrraaxxxiiiiiissss")
"aiiiprrssxxxssrrpiiia"```

This isn’t very good from an efficiency standpoint. The call to `string-append` is quadratic, and the algorithm as a whole generates a lot of garbage, not to mention the naive impolementation of `string-reverse`. A better approach modifies the string in-place, once the frequencies are known:

```(define (palin str)
(let ((freqs (make-vector 256 0)) (len (string-length str)))
(do ((cs (string->list str) (cdr cs))) ((null? cs))
(let ((i (char->integer (car cs))))
(vector-set! freqs i (+ (vector-ref freqs i) 1))))
(let loop ((i 0) (p 0) (center-char #f) (center-count 0))
(cond ((= 256 i)
(when center-char
(do ((j 0 (+ j 1))) ((= j center-count))
(string-set! str (+ p j) center-char)))
str)
((even? (vector-ref freqs i))
(do ((j 0 (+ j 1)))
((= j (/ (vector-ref freqs i) 2)))
(string-set! str (+ p j) (integer->char i))
(string-set! str (- len p j 1) (integer->char i)))
(loop (+ i 1) (+ p (/ (vector-ref freqs i) 2))
center-char center-count))
((not center-char)
(loop (+ i 1) p (integer->char i) (vector-ref freqs i)))
(else #f)))))

> (palin "pprrrraaxxxiiiiiissss")
"aiiiprrssxxxssrrpiiia"```

You can run the program at http://ideone.com/f05O6W.

Advertisement

Pages: 1 2

### 15 Responses to “Making A Palindrome”

1. wert310 said

(Emacs Lisp / Common Lisp)

Simple solution using the loop macro

```(defun palindrome-from-string (string)
(loop for ch across string
with singl = '()
and  chars = '()
do (cond ((member ch singl)
(setf singl (remove-if (lambda (c) (eql c ch)) singl))
(push ch chars))
(t (push ch singl)))
finally (cond ((<= (length singl) 1)
(return (apply #'string (append chars singl (reverse chars)))))
(t (return nil)))))
```

Same solution using named let

```(defun palindrome-from-string-nlet (string)
(nlet loop ((i 0)
(l (length string))
(singl '())
(chars '()))
(cond ((>= i l)
(if (<= (length singl) 1)
(apply #'string (append chars singl (reverse chars)))
nil))
((member (aref string i) singl)
(loop (+ i 1) l
(remove-if (lambda (c) (eql c (aref string i))) singl)
(cons (aref string i) chars)))
(t (loop (+ i 1) l (cons (aref string i) singl) chars)))))
```
2. Paul said

In Python.

```from collections import Counter
def is_odd(n): return n % 2 == 1
def make_palindrome(s):
counter = Counter(s)
odd_chars = (c for c, n in counter.items() if is_odd(n))
oddc = next(odd_chars, None)
if oddc and (not is_odd(len(s)) or next(odd_chars, None)):
return False
oddchars = counter.pop(oddc) * [oddc] if oddc else []
evenchars = [c * (n // 2) for c, n in counter.items()]
return "".join(evenchars + oddchars + evenchars[::-1])
```
3. Rutger said
```from collections import Counter
from collections import deque

def make_palindrome(s):
# validate
ctr = Counter(s)
middle_element = None
for a in ctr:
if ctr[a] % 2:
if not middle_element and ctr[a] % 2:
middle_element = a
else:
return None

# now make a palindrome
result = deque()
if middle_element:
result.append(middle_element)
ctr[middle_element] -= 1
for v in ctr:
for i in range(ctr[v]/2):
result.append(v)
result.appendleft(v)
return "".join(result)

print make_palindrome('123')
print make_palindrome('abcba')
print make_palindrome('abba')
print make_palindrome('bbbbb')
print make_palindrome('89282829282')

# output:
# None
# bacab
# baab
# bbbbb
# 22889298822
```
4. Jussi Piitulainen said

In brute force. Python’s interaction engine doesn’t print the None that indicates impossibility.

```>>> from itertools import permutations
>>> next((''.join(p) for p in permutations('pprraxxss') if p == p[::-1]), None)
'prxsasxrp'
>>> next((''.join(p) for p in permutations('pprraxxiss') if p == p[::-1]), None)
>>>
```
5. FA said

Dumm and Smart in Scala:

```package programmingpraxis

object MakingPalindrom {
def makePalindromSmart(in: String): String = {
val freq = in.groupBy(x => (x, in.filter(_ == x).size)).keys
val odds = freq.filter(x => x._2 % 2 == 1)
val evens = freq.filter(x => x._2 % 2 == 0)
if (odds.size > 1) "Not possible"
else {
val palindromEvensHalf = evens.map(x=>x._1.toString*(x._2/2)).reduce(_+_)
val odd = odds.map(x=>x._1.toString*(x._2)).reduce(_+_)
palindromEvensHalf+odd+palindromEvensHalf.reverse
}
}

def makePalindromDumm(in: String): String = {
if(in.permutations.filter(x=>x==x.reverse).isEmpty) "Not possible"
else in.permutations.filter(x=>x==x.reverse).mkString("\r\n")
}

makePalindromSmart("hello")                     //> res0: String = Not possible

makePalindromSmart("lhelloelh")                 //> res1: String = ellhohlle

makePalindromDumm("hello")                      //> res2: String = Not possible

makePalindromDumm("lhelloelh")                  //> res3: String = llheoehll
//| llehohell
//| lhleoelhl
//| lhelolehl
//| lelhohlel
//| lehlolhel
//| hlleoellh
//| hlelolelh
//| hellolleh
//| ellhohlle
//| elhlolhle
//| ehllollhe

}
```
6. Mike said

Python. The dictionary ‘odd’ is used like a flip-flop to keep track of whether a pair of characters has been seen. If so, add the character to ‘half’; otherwise, put the character in ‘odd’ to indicate it needs a match. At the end, if there is no more than one character that still needs a match, then a palindrome if formed by concatenating ‘half’ with the character than needs a match, if any, and half reversed. If there are more than one character needing a match, then no palindrome is possible.

```def makepalindrome(seq):
odd = {}
half = ''
for ch in seq:
if odd.pop(ch, False):
half += ch
else:
odd[ch] = True
if len(odd) < 2:
return half + ''.join(odd.keys()) + half[::-1]
```
7. Globules said

A Haskell version.

```import Data.List (group, partition, sort)

half :: [a] -> [a]
half xs = take (length xs `div` 2) xs

arrange :: [[a]] -> [[a]] -> [a]
arrange ess oss = let es = concatMap half ess
in es ++ concat oss ++ reverse es

palin :: Ord a => [a] -> Maybe [a]
palin xs = case partition (even . length) . group . sort \$ xs of
(_, _:_:_) -> Nothing
(ess, oss) -> Just \$ arrange ess oss

main :: IO ()
main = mapM_ (print . palin) ["", "a", "aa", "aaa", "aab",
"baab", "babab", "bababa"]
```
```\$ ./palin
Just ""
Just "a"
Just "aa"
Just "aaa"
Just "aba"
Just "abba"
Just "abbba"
Nothing
```
8. I am sure there would be an easier way to do this. But here is mine.

```public static String isPalindrome(String str){
String result="";
List<Character> chars = new LinkedList<>();
for(int i=0;i<str.length();i++)
chars.add(str.charAt(i));
chars.sort(null);
int single=0;
char midChar=str.charAt(str.length()-1);//default case if last character

for(int i=0;i<chars.size()-1;i++){
if(chars.get(i)!=chars.get(i+1)){
single++;
if(single<=1)
midChar=chars.get(i);
else
return "False";
}
else{
result=result.substring(0,result.length()/2)+chars.get(i)+chars.get(i)+result.substring(result.length()/2);
i++;
}
}
if(str.length()%2==1)
result=result.substring(0,result.length()/2)+midChar+result.substring(result.length()/2);

if(result.length()==str.length())
return result;
else
return "False";

}
```
9. Kevin said

I decided to try to do it in java in as few lines of code as possible. Here’s what I got (13 lines):

import java.util.HashMap;
class Main {
public static void main(String[] args) {
String input = “aaaabbbccdd”;
int numOdd = 0;
HashMap numChars = new HashMap();
for (int k = 0; k 1 ? “Nope!” : “Yup!”);
}
}

10. Kevin said

looks like 4 of the lines got cut out. Not sure why

11. Jussi Piitulainen said

@Kevin, paste your Java code between sourcecode tag lines like the following, or look for other workable ways to post source code in the top bar of this site.
``` [sourcecode lang="java"] [/sourcecode] ```
That should be two tag lines in square brackets. Your code between < and > confused a processor that was looking for either some HTML or else these square-bracketed tags (possibly other things that I don’t know about).

12. I enjoyed mike’s python solution. So I attempted to copy this concept to java

```public static String isPalin(String str){
List<String> odd = new ArrayList<>(); // I used a list instead of a dictionary.
String half="";
String mid = "";
for(int i =0;i<str.length();i++){
if(odd.contains(str.substring(i,i+1))){  //if odd contains character remove it and add to first half
odd.remove(str.substring(i,i+1));
half+=str.charAt(i);
}else odd.add(str.substring(i,i+1));  //else add to odd
}
for(String c:odd)
mid+=c;
if (mid.length()<2){
return half+mid+new StringBuilder(half).reverse().toString();
}
return "Not a Palindrome";
}
```
13. matthew said

Here’s another Haskell solution – sort first, then scan the list looking for pairs. Reject if more that one unmatched item found:

```import Data.List

palin s = makepal (sort s) [] [] where
makepal (a:b:s) t u =
if a == b then makepal s (a:t) u
else checkpal (b:s) t a u
makepal [a] t u = checkpal [] t a u
makepal [] t u = Just (reverse t ++ u ++ t)
checkpal s t a [] = makepal s t [a]
checkpal _ _ _ _  = Nothing

main = mapM_ (print . palin) ["", "a", "aa", "aaa", "aab", "baab",
"babab", "aabbc", "abbcc", "bababa"]
```
14. alifaki said

“`
from itertools import permutations
def make_palindrome(word):
perms = list(permutations(word))
for i in perms:
if ”.join(i) == ”.join(i)[::-1]:
return ”.join(i)
return False
“`

15. fisherro said
```#include <algorithm>
#include <boost/algorithm/string.hpp>
#include <boost/optional.hpp>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

boost::optional<std::string> make_palindrome(std::string input)
{
boost::algorithm::to_lower(input);
boost::optional<std::string> result;
std::string palindrome;
boost::optional<char> odd_man_out;
//For each character...
for (auto i = input.begin(); i != input.end(); ++i) {
//Look for a matching character.
auto match = std::find(i + 1, input.end(), *i);
if (match != input.end()) {
//If we find it, remove it from input, & add it to palindrome.
input.erase(match);
palindrome.push_back(*i);
} else {
//If we don't find it,
if (!odd_man_out) {
//If we don't have an odd-man-out, we do now.
odd_man_out = *i;
} else {
//If we already have an odd-man-out, no palindrome.
return result;
}
}
}
std::string copy(palindrome);
if (odd_man_out) palindrome += *odd_man_out;
std::copy(copy.rbegin(), copy.rend(),
std::back_inserter(palindrome));
return palindrome;
}

int main(int argc, char** argv)
{
std::vector<std::string> args(argv + 1, argv + argc);
if (args.size() < 1) {
args = {
"racecar",
"aaccerr",
"aabbccdd",
"boost",
};
}
for (auto arg: args) {
auto palindrome = make_palindrome(arg);
std::cout << '"' << arg << "\": ";
if (palindrome)
std::cout << '"' << *palindrome << "\"\n";
else
std::cout << "Cannot become a palindrome.\n";
}
}
```