class Solution { //make a pair class to store char,frequency class pair implements Comparable<pair>{ char ch ; int freq; pair(char ch , int freq){ this.ch = ch; this.freq = freq; } public int compareTo(pair o ){ //descending order return o.freq - this.freq; } } public String reorganizeString(String s) { //make a maxheap to get value based on maximum frequency Queue<pair> maxheap = new PriorityQueue<>(); //create and store frequency HashMap<Character,Integer> map = new HashMap<>(); for(char ch : s.toCharArray()) map.put(ch ,map.getOrDefault(ch,0)+1); //adding character,frequency to max heap for(char key : map.keySet()){ pair p = new pair(key , map.get(key)); maxheap.add(p); } StringBuilder ans = new StringBuilder(); pair block = maxheap.remove(); //adding first letter in our string ans.append(block.ch); block.freq = block.freq - 1; while(maxheap.size()!=0){ pair temp = maxheap.remove(); ans.append(temp.ch); temp.freq = temp.freq-1; //check if frequency has got to zero if(block.freq != 0) maxheap.add(block); block = temp; } //if block element still has any frequency ,no string exists if(block.freq > 0 ) return ""; return ans.toString(); } }