Reorganize String

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = “aab”
Output: “aba”

Example 2:

Input: s = “aaab”
Output: ""

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Approach

• first we create a frequency map then we create a priority queue with condition that it should be order by frequency descending also the queue is of element and their frequency as array
• then just poll two element at a time so it will make sure they are not the same then append it to the string then reduce their frequency
• also when we offer after reducing frequency so you previously polled the same element now we are adding again so don’t get confused here
• Time and space O(n)

class Solution {
    public String reorganizeString(String s) {
        int[] freq = new int[26];
        for (char c: s.toCharArray()) {
            freq[c - 'a']++;
        }
 
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> b[1] - a[1]); //order desc freq
        for(int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                if (freq[i] > (s.length() + 1)/2)
                    return ""; // not possible to have adjacent diff
                heap.offer(new int[]{i,freq[i]});    
            }
        }
 
        StringBuilder ans = new StringBuilder();
        while (heap.size() >= 2) {
            int[] first = heap.poll();
            int[] second = heap.poll();
            ans.append((char)(first[0] + 'a'));
            ans.append((char)(second[0] + 'a'));
            if (--first[1] > 0)
                heap.offer(first);
            if (--second[1] > 0)
                heap.offer(second);
        }
 
        if (!heap.isEmpty()) {
            ans.append((char) (heap.poll()[0] + 'a'));
        }
 
        return ans.toString();
    }
}