CareerCup

An O(n) solution in code:

string S = "aabbccd";
int count[26];
memset(count, 0, sizeof(count));

for(int i = 0; i < S.size(); i++){
    count[S[i] - 'a']++;
}

int odds = 0;

for(int i = 0; i < 26; i++){
    if(count[i] % 2 == 1){
        odds++;
    }
}

return odds <= 1;

Count the number of occurrences of each character. Let A the number of characters that have an odd number of occurrences in the string. You can shuffle for palindrome if:

A = 0 or A = 1

string S = "aabbccd";
int count[26];
memset(count, 0, sizeof(count));

for(int i = 0; i < S.size(); i++){
count[S[i] - 'a']++;
}

int odds = 0;

for(int i = 0; i < 26; i++){
if(count[i] % 2 == 1){
odds++;
}
}

return odds <= 1;

private static final int ASCII_MAX = 255;
	
	boolean canBePalindrome(String str){
		checkNotNull(str, "'str' is NULL");
		
		BitSet foundChars = new BitSet(ASCII_MAX+1);
		
		int strLength = str.length();
		int chCode;
		
		for( int i =0; i < strLength; i++){
			chCode = str.charAt(i);			
			checkArgument(chCode <= ASCII_MAX, "Not an ascci character found, code: " + chCode);			
			foundChars.flip(chCode);
		}
		
		boolean isStrLengthOdd = (str.length() & 1) != 0;
		int foundCharsCardinality = foundChars.cardinality();
		
		return (isStrLengthOdd && foundCharsCardinality == 1 ) || (! isStrLengthOdd && foundCharsCardinality == 0 );		
	}

For a string to form palindrome, number of character occuring odd number of times should be <= 1. For example, aabbaa(0 odd chars) or aabaa or abcccba (1 odd chars).
So this problem can be reduced to find the number of characters occurring odd number of times <= 1.

There are 2 solutions I can think of
1) Sort the characters and count the number of times each character occurs.
Complexity O(nlogn + n) = O(n log n )
2) Hash the characters with number of times they occur and check how many characters occur odd number of times = O(n + number of unique chars) = O(n)

Find frequency of each characters.
If the number of characters wtih odd frequence <= 1 then YES else NO

import java.util.Arrays;

/* Program to check if Anagram of a String is a palindrome or not*/
public class AnagramOfStringIsPalindrome {
	public static void main(String arr[]){
		String str = "aabbcdcaa11";
		System.out.println(isPalindrome(str));
	}
	public static String isPalindrome(String str){
		/* Converting String to Array and sorting it */
		char[] a = str.toCharArray();
		Arrays.sort(a);
		int uniqueCount = 0;
		/* Check if adjacent elements after sorting match */
		/* Keep a count of no of elements that dint match if its just one its still a palindrome */
		for(int i=0;i<a.length-1;){
			if(a[i] == a[i+1]){
				i += 2; continue;
			}else{
				uniqueCount++;
				if(uniqueCount>1)
					return "Not a Palindrome";
			}
		}
		return "Is Palindrome";
	}
}

import java.util.*;
public class palindrome {

public static void main(String[] args) {
String str="abcdcba";
int count=0;
Map<Character,Integer> hmap=new HashMap<Character,Integer>();
for(int i=0;i<str.length();i++)
{
if(hmap.containsKey(str.charAt(i)))
hmap.put(str.charAt(i),hmap.get(str.charAt(i))+1);
else
hmap.put(str.charAt(i), 1);

}

Set set=hmap.entrySet();
Iterator itr=set.iterator();
while(itr.hasNext())
{
Map.Entry me=(Map.Entry)itr.next();
Integer i=(Integer)me.getValue();
if(i%2!=0)
count++;

}
if(count==1||count==0)
System.out.println("can be palindrome");
else
System.out.println("not palindrome");
}
}

import java.util.*;
public class palindrome {
	
	public static void main(String[] args) {
	String str="abcdcba";
	int count=0;
	Map<Character,Integer> hmap=new HashMap<Character,Integer>(); 
	for(int i=0;i<str.length();i++)
	{
		if(hmap.containsKey(str.charAt(i)))
		hmap.put(str.charAt(i),hmap.get(str.charAt(i))+1);
		else
			hmap.put(str.charAt(i), 1);
		
	}
	
	Set set=hmap.entrySet();
	Iterator itr=set.iterator();
	while(itr.hasNext())
	{
		Map.Entry me=(Map.Entry)itr.next();
		Integer i=(Integer)me.getValue();
		if(i%2!=0)
			count++;
			
	}
	if(count==1||count==0)
		System.out.println("can be palindrome");
	else
		System.out.println("not palindrome");
}
}

package com.test;

public class PolindromString {

	public static void main(String[] args) {
		// TODO Check Polindrom
		boolean p=true;
		String s="assa";
		int k=s.length()-1;
		for(int i=0; i<=k;i++,k--){
			
			if (s.charAt(i)!=s.charAt(k)){
				p=false;
				break;
			}
			
		}
if(p&s.length()!=0)
	System.out.println(s+" is palindrom");
else 
	System.out.println(s+" is not palindrom");

	}

}

package com.test;

public class PolindromString {

	public static void main(String[] args) {
		// TODO Check Polindrom
		boolean p=true;
		String s="assa";
		int k=s.length()-1;
		for(int i=0; i<=k;i++,k--){
			
			if (s.charAt(i)!=s.charAt(k)){
				p=false;
				break;
			}
			
		}
if(p&s.length()!=0)
	System.out.println(s+" is palindrom");
else 
	System.out.println(s+" is not palindrom");

	}

}

package com.test;

public class PolindromString {

	public static void main(String[] args) {
		// TODO Check Polindrom
		boolean p=true;
		String s="assa";
		int k=s.length()-1;
		for(int i=0; i<=k;i++,k--){
			
			if (s.charAt(i)!=s.charAt(k)){
				p=false;
				break;
			}
			
		}
if(p&s.length()!=0)
	System.out.println(s+" is palindrom");
else 
	System.out.println(s+" is not palindrom");

	}

}