767. Reorganize String – SOFTWARE ENGINEERING

/**

* 767. Reorganize String

* Given a string S, check if the letters can be rearranged so that two characters that are adjacent

* to each other are not the same.

* If possible, output any possible result. If not possible, return the empty string.

* Example 1:

* Input: S = “aab”

* Output: “aba”

See my solution to this problem here : https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/ReorganizeString.java

Question requires reorganizing the string such that no two characters are adjacent to each other. The question requires identifying that you have to take the current most frequent characters and start spacing them out until no more characters are left. As you space the characters out their frequency will decrease, hence need to work on characters which currently have the highest frequency.

The reason to work on most frequent characters first is because they will repeat most often and hence need to be washed out at the earliest.

By definition, this logic will work as long as a largest character frequency is not greater than ((total number of characters + 1) / 2). I,e in aab, you can write it as aba. But you cant process aaab.

The problem requires using a priority queue that’s sorted first by frequency and then by alphabetical order.

This problem has a pattern that often repeats.

Here is the code solution:

public String reorganizeString(String s) {
    int [] charCount = new int [26];
    for (int i = 0; i < s.length(); i++) {
        charCount[s.charAt(i)-'a'] += 1;
    }
    PriorityQueue<Pair<Character, Integer>> pq = new PriorityQueue<>((first, second) -> {
        if (first.second.equals(second.second)) {
            return Character.compare(first.first, second.first);
        }
        return Integer.compare(second.second, first.second); //move high count items on top
    });
    int len = s.length();
    for (int i =0; i < charCount.length; i++) {
        int count = charCount[i];
        if (count ==0) continue;
        if (count > (len+1)/2) { //edge case to ensure count that cant be handled by the algo
            return "";
        }
        Character ch = (char) ( 'a' + i);
        pq.add(new Pair<>(ch, count));
    }
    StringBuilder builder = new StringBuilder();
    while (pq.size() >= 2) {
        Pair<Character, Integer> first = pq.poll();
        Pair<Character, Integer> second = pq.poll();
        builder.append(first.first);
        builder.append(second.first);
        if (first.second > 1) {
            Pair<Character, Integer> firstM = new Pair<>(first.first, first.second - 1);
            pq.add(firstM);
        }
        if(second.second > 1) {
            Pair<Character, Integer> secondM = new Pair<>(second.first, second.second - 1);
            pq.add(secondM);
        }
    }
    if (!pq.isEmpty()) {
        Pair<Character, Integer> lastItem = pq.poll();
        builder.append(lastItem.first);
    }
    return builder.toString();
}