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

    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";
        }
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: