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: "" } }
Leave a Comment