Alternate string characters

Problem

Given a string, return a string with the same characters but re-arranged in such a way that there are no adjacent characters that are the same. If it’s not possible, return null.

Example:

Input: "bbaaac"
Output: "ababac"

Input: "baaa"
Output: null

Approach

A brute force solution to this problem can be implemented by keeping a HashMap with a count of all the characters, and then repeatedly select the character with the highest occurrence (that has not been selected before) until there are no more characters to be selected. If we are left with a letter that has a count of more than 1 then return null. This solution takes O(n^2) because to find the character with the highest occurrence we need to scan all the keys of the HashMap (n) and we need to repeat the operation n times, hence O(n^2) total.

Solution

Since the main operation of the brute force algorithm is to always select the letter with the highest count, we can use a heap to maintain the running count of each letter. We can then repeatedly extract the top element of the heap, decrement its count, and then re-insert the letter in the heap if the count is greater than zero. To avoid extracting the same character twice in a row we can re-insert each letter after extracting the following letter so that we can be sure that the same letter is not visited twice in a row.

Because insertion in a heap takes O(logn) and we need to repeat this operation for all the letters in the input string (n) the total runtime of this algorithm is O(nlogn).

How much is space complexity? One would be tempted to say O(n) because we need to store all the letters in the input string along with their count. However, the maximum size of the HashMap will be the size of the entire alphabet in case the input string contains all the characters of the given alphabet. Because we can assume that the alphabet, however big, is of fixed size the space complexity is O(1).

String alternateCharacters(String str) {
  if (str == null || str.isEmpty()) {
      return null;
  }

  HashMap<Character, Integer> counter = countOccurrences(str);

  // add all characters and counts in the priority queue
  PriorityQueue<HeapNode> queue = initializeQueue(counter);

  // Use a list to store characters and then join into a string
  // at the end to avoid the extra complexity of concatenating
  // one character at a time
  List<Character> result = new ArrayList<>();

  HeapNode currentNode = queue.poll();
  result.add(currentNode.getKey());
  currentNode.decrementCounter();

  while(!queue.isEmpty()) {
      HeapNode nextNode = queue.poll();

      result.add(nextNode.getKey());
      nextNode.decrementCounter();

      if (currentNode.getValue() > 0) {
          queue.add(currentNode);
      }

      currentNode = nextNode;
  }

  if (currentNode.getValue() > 0) {
      return null;
  } else {
      return result.stream().map(String::valueOf).collect(Collectors.joining());
  }
}

// Store each key,value pairs in the priority queue
PriorityQueue<HeapNode> initializeQueue(HashMap<Character, Integer> counter) {
  PriorityQueue<HeapNode> queue = new PriorityQueue<>();

  for (HashMap.Entry<Character, Integer> entry : counter.entrySet()) {
      queue.add(new HeapNode(entry.getKey(), entry.getValue()));
  }

  return queue;
}

// Count all character occurrences of the input string
HashMap<Character, Integer> countOccurrences(String str) {
  HashMap<Character, Integer> counter = new HashMap<>();

  for (Character c : str.toCharArray()) {
      counter.put(c, counter.getOrDefault(c, 0)+1);
  }

  return counter;
}

// This class reprensents a node in the Heap
class HeapNode implements Comparable<HeapNode> {
  private Character key;
  private int value;

  public HeapNode(Character key, Integer value) {
      this.key = key;
      this.value = value;
  }

  public void decrementCounter() {
      this.value--;
  }

  public Character getKey() {
      return this.key;
  }

  public int getValue() {
      return this.value;
  }

  @Override
  public int compareTo(HeapNode o) {
      return o.value - this.value;
  }
}