## Making A Palindrome

### September 29, 2015

We have today a small exercise in string manipulation: Given an input string, either return a string containing the same characters but arranged to form a palindrome, or indicate that no such rearrangement is possible.

Your task is to write the program that creates a palindrome. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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

```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="";
for(int i=0;i<str.length();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);
}
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";
}
}
```