Untitled

import java.util.*;

public class ReorganizeString {
    public String reorganizeString(String s) {
        int[] freq = new int[26]; // Frequency count
        
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        
        int n = s.length();
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                // If a character appears more than (n+1)/2 times, return ""
                if (freq[i] > (n + 1) / 2) return "";
                maxHeap.add(new int[]{i, freq[i]});
            }
        }

        StringBuilder result = new StringBuilder();
        int[] prev = {-1, 0}; // To store last used character

        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll(); // Most frequent character
            result.append((char) (curr[0] + 'a'));
            curr[1]--; // Decrease frequency

            if (prev[1] > 0) {
                maxHeap.add(prev); // Push back previous character if available
            }

            prev = curr; // Update previous character
        }

        return result.toString();
    }

    public static void main(String[] args) {
        ReorganizeString obj = new ReorganizeString();
        System.out.println(obj.reorganizeString("aab"));  // Output: "aba"
        System.out.println(obj.reorganizeString("aaab")); // Output: ""
    }
}