CareerCup

the idea is:

1) build a Map<K,V> where K = char present in String, V = num. of occurrences of char
2) validate if palindrome can be generated by rule: all counts for each char must be even, except 1 char that can have an odd count of occurences.
3) if palindrome can be generated, build a new string distributing each group of chars at the start and end of string, if there is an odd count of a specific char C place C at the middle of String, and distribute the remaining.
4) return resulting string.

Solution in Java:

import java.util.*;

public class Solution {

	public static String getPalindromeIfPresent(String s) {

		// Basic validation
		if (s == null || s.length() < 2 || s.equals("") ) {
		    return null;
		}
		Map<Character, Integer> mapChars = new HashMap<Character, Integer>();

		char[] chars = s.toCharArray();

		// Build map of each char and count occurences in String
		for (int i = 0; i < chars.length; i++) {
		    if (mapChars.containsKey(chars[i])) {
		        Integer val = mapChars.get(chars[i]);
		        mapChars.put(chars[i], val+1);
		    } else {        
		        mapChars.put(chars[i], 1);    
		    }
		}

		// Validate String if possible to form palindrome rule is:
		// must have all chars count even, except middle char which can be odd
		int oneCharCount = 0;
		for (Map.Entry<Character, Integer> entry : mapChars.entrySet()) {
		    if (entry.getValue() % 2 != 0) {
		        oneCharCount++;
		        
		        if (oneCharCount > 1) {
		            return null;
		        }
		    }
		}

		int sLen = s.length();
		int middle = sLen/2;   
		Character midChar = null;
		StringBuilder s1 = new StringBuilder();

		// rearrange each group of chars distributing them at the start and end of string 
		for (Map.Entry<Character, Integer> entry : mapChars.entrySet()) {
		    int charCount = entry.getValue();
		    Character c = entry.getKey();
		    
		    if (charCount % 2 != 0) {
		        midChar = c;
		    }
		    
		        int i = charCount / 2;
		        while (i > 0) {
		           s1.append(c);
		           s1.insert(0, c);
		           i--;
		        }                              
		}

		// if middle Char exists from odd count, place it otherwise ignore
		if (midChar != null) {
			s1.insert(middle, midChar);	
		}

		return s1.toString();
    }
	
    public static void main(String[] args) {
    	String test = "abb";
    	System.out.println(getPalindromeIfPresent(test));

    	String test2a = "bbaa";
    	System.out.println(getPalindromeIfPresent(test2a));

    	String test2 = "nvreeodorevdne";
    	System.out.println(getPalindromeIfPresent(test2));

    	String test3 = "earth1earth";
    	System.out.println(getPalindromeIfPresent(test3));
    }
}

#include<stdio.h>
#include<string.h>
int arr[256];
void main()
{
char str[50],index;
int i,j=0,len,k=0,oddcount=0;

scanf("%s",str);
len=strlen(str);
for(i=0;i<len;i++)
arr[str[i]]++;

for(i=0;i<256;i++)
{
if(arr[i]%2!=0)
{
oddcount++;
index=(char)i;
}
}
if((len%2==0 && oddcount==0) || (len%2!=0 && oddcount==1))
{
(oddcount==1)?str[len/2]=index:printf("\n");
for(i=0;i<256;i++)
{
if(arr[i]>0)
{
for(j=0;j<arr[i]/2;j++)
{
str[k]=str[len-1-k]=(char)i;
k++;
}

}

}

printf("\n String is : %s",str);
}else
printf("sorry can't make palindrome");
}

public String arrange(String value) {
char[] data = value.toCharArray();

// check the char value range
char largestChar = data[0];
char smallestChar = data[0];
for(char curr : data) {
if(curr > largestChar)
largestChar = curr;
if(curr < smallestChar)
smallestChar = curr;
}
int[] counters = new int[largestChar - smallestChar + 1];

// generate the char counters
for(char curr : value.toCharArray()) {
int index = curr - smallestChar;
counters[index] ++;
}

// detect palindrome by assigning the palindrome array symmetrically
char[] palindrome = new char[value.length()];
int palindromeOffset = 0; // point to next used space
for(int i = 0; i < counters.length; i ++) {
char charValue = (char) (smallestChar + i);
int count = counters[i];
if(count % 2 == 0) {
// the amount of current char is even number

// symmetrically set the char in palindrome
count /= 2;
while(count > 0) {
palindrome[palindromeOffset] = charValue;
palindrome[palindrome.length - palindromeOffset - 1] = charValue;
palindromeOffset ++;
count --;
}
} else {
// the amount of current char is odd number
if(palindrome.length % 2 == 0 || palindrome.length % 2 == 0 && palindrome[palindrome.length/2] != 0)
// palindrome's length is even number
// or palindrome.length is odd number, the only central char has been occupied
// (palindrome only allows on char is in odd number)
return null;
palindrome[palindrome.length/2] = charValue;

// symmetrically set the char in palindrome
count /= 2;
while(count > 0) {
palindrome[palindromeOffset] = charValue;
palindrome[palindrome.length - palindromeOffset - 1] = charValue;
palindromeOffset ++;
count -- ;
}
}

}
return new String(palindrome);
}

public String arrange(String value) {
        char[] data = value.toCharArray();

        // check the char value range
        char largestChar = data[0];
        char smallestChar = data[0];
        for(char curr : data) {
            if(curr > largestChar)
                largestChar = curr;
            if(curr < smallestChar)
                smallestChar = curr;
        }
        int[] counters = new int[largestChar - smallestChar + 1];

        // generate the char counters
	for(char curr : value.toCharArray()) {
		int index = curr - smallestChar;
		counters[index] ++;
	}

        // detect palindrome by assigning the palindrome array symmetrically
	char[] palindrome = new char[value.length()];
        int palindromeOffset = 0; // point to next used space
	for(int i = 0; i < counters.length; i ++) {
	    char charValue = (char) (smallestChar + i);
            int count = counters[i];
            if(count % 2 == 0) {
                // the amount of current char is even number
                
                // symmetrically set the char in palindrome
                count /= 2;
                while(count > 0) {
                    palindrome[palindromeOffset] = charValue;
                    palindrome[palindrome.length - palindromeOffset - 1] = charValue;
                    palindromeOffset ++;
                    count --;
                }
            } else {
                // the amount of current char is odd number
                if(palindrome.length % 2 == 0 || palindrome.length % 2 == 0 && palindrome[palindrome.length/2] != 0)
                    // palindrome's length is even number
                    // or palindrome.length is odd number, the only central char has been occupied
                    // (palindrome only allows on char is in odd number)
                    return null;
                palindrome[palindrome.length/2] = charValue;

                // symmetrically set the char in palindrome
                count /= 2;
                while(count > 0) {
                    palindrome[palindromeOffset] = charValue;
                    palindrome[palindrome.length - palindromeOffset - 1] = charValue;
                    palindromeOffset ++;
                    count -- ;
                }
            }

	}
	return new String(palindrome);
}

Sorry for the first submit where the code whitespaces are totally messed up.

O(n) time and O(n) space

string get_palindrome(string str)
{
	if( str.length()<2 ) return str;
	
	/* build hashmap with key:char value:count. Takes O(n) time and O(n) space */
	unordered_map<char,int> hmap;
	for(int i=0; i<str.length(); i++) 
		hmap[str[i]]++;

	/* find the number of odd elements. Takes O(n) */
	int odd_cnt=0; char odd_char;
	unordered_map<char,int>::iterator it;
	for(it=hmap.begin(); it!=hmap.end(); it++) {
		if( it->second%2 ) {
			odd_cnt++;
			odd_char = it->first;
		}
	}

	/* odd_cnt=1 only if the length of str is odd */
	if( odd_cnt>1 || odd_cnt==1&&str.length()%2==0 )
		return "NO PALINDROME";

	/* generate palindrome. Takes O(n) */
	string palindrome;
	if( odd_cnt ) {
		pair<char,int> kv = *(hmap.find(odd_char));
		hmap.erase(odd_char);
		for(int i=0; i<kv.second; i++)
			palindrome += kv.first;
	}
	while(!hmap.empty()) {
		pair<char,int> kv = *(hmap.begin());
		hmap.erase(hmap.begin());
		for(int i=0; i<kv.second; i+=2) {
			palindrome = kv.first + palindrome + kv.first;
		}
	}
	return palindrome;
}

Some c# code:

public static string BuildPalindrome(string input)
        {
            if (String.IsNullOrEmpty(input))
                throw new ArgumentException("input");
            var alph = Enumerable.Repeat(0, 255).ToArray();
            var palindrome = new char[input.Length];
            foreach (var t in input)
                alph[t]++;
            var position = 0;
            var flag = false;
            for (var i = 0; i < 255; i++)
            {
                if (alph[i] % 2 != 0)
                {
                    if (flag)
                        return "-1";
                    flag = true;
                    alph[i]--;
                    palindrome[input.Length/2] = (char) i; 
                }
                while (alph[i] != 0)
                {
                    palindrome[position] = palindrome[input.Length - 1 - position] = (char) i;
                    alph[i] -= 2;
                    position++;
                }
            }
            return String.Join("", palindrome);
        }

public String getPalindrome(String s) {
	if (s == null)
		return null;
	Map<Character, Integer> letters = new HashMap<Character, Integer>();
	for (int i = 0; i < s.length(); i++) {
		char c = s.charAt(i);
		if (!letters.containsKey(c))
			letters.put(c, 1);
		else
			letters.put(c, letters.get(c) + 1);
	}
	char[] result = new char[s.length()];
	int i = 0, j = result.length - 1;
	Character middle = null;
	for (Entry<Character, Integer> e : letters.entrySet()) {
		int val = e.getValue();
		char c = e.getKey();
		if (val % 2 != 0) {
			if (middle == null && s.length() % 2 != 0) {
				middle = c;
				val--;
			} else
				return "-1";
		}
		for (int k = 0; k < val / 2; k++) {
			result[i++] = c;
			result[j--] = c;
		}
	}
	if (middle != null)
		result[result.length / 2] = middle;
	return new String(result);
}

Sort the string and swap contiguous elements to the beginning and to the end.
Complexity

O ( N long N ) + O ( N )

Space complexity O ( 2N )

public static String getPalindrome(char str []){
	char [] result = new char[str.length];
	Arrays.sort(str);
	boolean isEven = (str.length % 2 == 0);
	int start  =0;
	int end = str.length -1;
	char reminder = ' ';
	for(int i = 1; i < str.length; i+=2){
		if(str[i-1] != str[i]){
			if(isEven){
				return "-1";
			}else{
				reminder = str[i-1];
				isEven = true;
			}
		}else{
			result[start++] = str[i];
			result[end--] = str[i-1];
		}
		if(i+1 == str.length-1) // special case when is not even and reminder is the last one
			reminder = str[i+1];
	}
	
	if(start == end){
		result[start] = reminder;
	}
	return new String(result);
}
public static void main(String [] args){
	System.out.println(getPalindrome(args[0].toCharArray()));
}

import java.util.HashMap;
import java.util.Set;

public class ReArrangeToPalindrome {

	HashMap<Character, Integer> hmp = new HashMap<Character, Integer>();

	public void isPalindromePossible(String str) {
		int i = 0;
		char[] ch = str.toCharArray();
		if (ch.length == 0) {
			System.out.println("Empty String");
			return;
		} else if (ch.length == 1) {
			System.out.println("---PalinDrome---");
			return;
		}

		while (i != ch.length) {

			if (hmp.containsKey(ch[i])) {
				hmp.put(ch[i], hmp.get(ch[i]) + 1);
			} else {
				hmp.put(ch[i], 1);
			}
			i++;
		}

		findPalinDrome();

	}

	public void findPalinDrome() {
		Set<Character> ch1 = hmp.keySet();
		int k = 0;
		for (Character ch : ch1) {

			if (hmp.get(ch) % 2 == 0) {

			} else {
				k++;
				if (k % 2 == 0) {
					System.out.println("---No Palindrome---");
					return;
				}

			}

		}
		System.out.println("---PalinDrome---");

	}

	public static void main(String[] args) {

		ReArrangeToPalindrome rp = new ReArrangeToPalindrome();
		String str = "axcdbcacba";
		rp.isPalindromePossible(str);

	}

}

Consider 2 cases:
1) String contains odd number of characters. Then the number of all characters in the string should be even except one character which is located in the middle.
2) String contains even number of characters. Then all characters should be even.

For simplicity I assumed that there are only English capital letters. If not its minor fix to change it.

public static void main(String[] args) {
        String s = "AABB";
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'A']++;
        }
        int middleChar = -1;
        StringBuilder sb = new StringBuilder(s.length());
        int i = 0;
        for (i = 0; i < count.length; i++) {
            if (count[i] % 2 == 1) {
                if (count[i] == 1 && middleChar == -1) {
                    middleChar = i;
                    count[i]--;
                } else {
                    break;
                }
            } else if (count[i] != 0) {
                for (int j = 0; j < count[i] / 2; j++) {
                    sb.append((char) (i + 'A'));
                    count[i]--;
                }
            }
        }
        if (i != count.length) {
            System.out.println("Could not create the palindrome.");
            return;
        }
        if (middleChar != -1) {
            sb.append((char) (middleChar + 'A'));
        }
        i = count.length - 1;
        while (i >= 0) {
            if (count[i] == 0) {
                i--;
                continue;
            }
            sb.append((char) (i + 'A'));
            count[i]--;
            if (count[i] == 0) {
                i--;
            }
        }
        System.out.println(sb);
    }