This is a problem from Leetcode called Reorganize String that was classified has “Medium”. Here, we receive a String s which has lowercase letters only. The objetive here is to outcome an anagram based on String s (rearrange its letters) so no same letters appear together.

(You may take some time to try out the question first! :))

Let’s go to the solution then!

For this solution, we created an object called Node, which stores the letter and the number of times we’ve seen it.

public class Node {
    int count;
    char letter;

    public Node(char letter, int count) {
        this.letter = letter;
        this.count = count;
    }
}

For the main solution, we created and function called reorganizeString which takes the string, counting each letter through an array of size 26. (We are considering an alphabeth having only 26 characters, as the string is all lowercase and english based). We also created an heap to order by the number of times a letter exists in the original string (the object for heaps in Java is PriorityQueue). We offer new Nodes, based on the letters and theirs counting in the string. What we need for this solution is create an anagram, that each letter does not have the same letter close to it. For this, we can take two letter from the heap each time. They must be different, and we concatenate them on the answer, we can now decrease one from each of these characters, and add back to the heap. We must do that until the heap is empty or has only one element. Then, if we found a single character is left, we need to put it into the answer as well. Java has some problems to consider mutable strings, as the current object String is immutable, we use StringBuilder to decrease the number of partial answers, as their string creation will take much more time.

public String reorganizeString(String s) {

    // Count letters
    int[] letters = new int[26];
    for (char l: s.toCharArray()) {
        letters[l-'a']++;
    }
    
    // Sort letters
    PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> {
        if (a.count != b.count) 
            return b.count - a.count;
        
        return a.letter - b.letter;
    });
    
    int n = s.length();
    for (int i = 0; i < letters.length; i++) {
        if (letters[i] > (n+1) / 2)
            return "";
        
        if (letters[i] > 0) 
            pq.offer(new Node((char)('a' + i), letters[i]));
    }
    
    // Build an anagram
    StringBuilder sb = new StringBuilder();
    char last = ' ';
    while (pq.size() >= 2) {
        Node node1 = pq.poll();
        Node node2 = pq.poll();
        
        sb.append(node1.letter);
        sb.append(node2.letter);
        
        if (--node1.count > 0) pq.add(node1);
        
        if (--node2.count > 0) pq.add(node2);
    }
    
    if (pq.size() > 0) {
        sb.append(pq.poll().letter);
    }
    
    return sb.toString();
}