Q63 Reorganize String - LeetCode

PHOTO EMBED

Sat Feb 04 2023 07:21:20 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

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();
        
    }
}





















content_copyCOPY

https://leetcode.com/problems/reorganize-string/