NoConsecutiveRepeatCharacters.java

public class NoConsecutiveRepeatCharacters {

  public static void main(String[] args) {
  	String input = "aaaaaabbbbcc";
  
  	//Sort the characters with highest freq. to the top
  	PriorityQueue<CharacterFrequencyNode> maxheap = new PriorityQueue<CharacterFrequencyNode>(new Comparator<CharacterFrequencyNode>() {
	  	@Override
	  	public int compare(CharacterFrequencyNode o1, CharacterFrequencyNode o2) {
	  		if(o1.frequency > o2.frequency){
	  		return -1;
	  		}
	  		else if(o1.frequency < o2.frequency){
	  			return 1;
	  		}
	  		else{
	  			return 0;
	  		}
	  	}
  	});
  HashMap<Character, Integer> charCount = new HashMap<Character,Integer>();
  
  for(int i =0;i<input.length(); i++){
  	char c = input.charAt(i);
  	if(charCount.containsKey(c)){
  		charCount.put(c,new Integer(charCount.get(c)+1));
  	}
  	else{
  		charCount.put(c,1);
  	}
  }
  
  for(Character c : charCount.keySet()){
  	CharacterFrequencyNode node = new CharacterFrequencyNode();
  	node.a = c;
  	node.frequency = charCount.get(c);
  	if(node.frequency > input.length()/2+1){
  		System.out.println("Output not valid");
  		System.exit(0);
  	}
  	maxheap.add(node);
  }
  
  StringBuffer sb = new StringBuffer();
  int i=0;
  while(!maxheap.isEmpty()){
  	CharacterFrequencyNode firsttemp = maxheap.poll();
		CharacterFrequencyNode secondtemp = maxheap.poll();
  	if(firsttemp != null){
  		sb.append(firsttemp.a);
  	firsttemp.frequency--;
  	if(firsttemp.frequency>0){
  		maxheap.add(firsttemp);
  	}
  }
  if(secondtemp != null) {
  sb.append(secondtemp.a);
  secondtemp.frequency--;
  if(secondtemp.frequency>0) {
  maxheap.add(secondtemp);
  }
  }
  
  }
  System.out.print("The output is: "+ sb.toString());
  }
  
  public static class CharacterFrequencyNode{
  Character a;
  int frequency;
  }
}