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.

&nbsp;
Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""

&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 500
	s consists of lowercase English letters.


class Solution:
	def reorganizeString(self, s: str) -> str:
		c = Counter(s)  # for counting the distinct element 
		pq = []
		for k,v in c.items(): heapq.heappush(pq,(-v,k))  #multipy by -1 to make max heap 
		ans = ''
		while pq :
			c, ch = heapq.heappop(pq)
			if ans and ans[-1] == ch: 
				if not pq: return '' // if heap is empty we cant make the ans return empty string
				c2, ch2 = heapq.heappop(pq)
				ans += ch2
				c2 += 1
				if c2: heapq.heappush(pq,(c2,ch2))
			else:
				ans += ch
				c += 1
			if c: heapq.heappush(pq,(c,ch))
		return ans
class Solution {
    public String reorganizeString(String s) {
        StringBuilder ans=new StringBuilder("");
        char[] charArray=new char[s.length()];
        Map<Character,Integer> hashMap=new HashMap<>();
        Queue<CharOccurence> queue=new PriorityQueue<>((a,b)->b.occurence-a.occurence);

        charArray=s.toCharArray();

        for(int i=0;i<charArray.length;i++)
        {
            Integer occurence=hashMap.get(charArray[i]);
            if(occurence==null)
                hashMap.put(charArray[i],1);
            else
                hashMap.put(charArray[i],occurence+1);
        }
        queue.addAll(hashMap.entrySet()
                     .stream()
                     .parallel()
                     .map(e->new CharOccurence(e.getKey(),e.getValue()))
                     .collect(Collectors.toList()));
        while(!queue.isEmpty())
        {
            Queue<CharOccurence> tmpQueue=new LinkedList<>();
            int sizeQueue=queue.size();
            int stringLength=ans.length();
            int startSub=(stringLength-1<0)?0:stringLength-1;
            int endSub=stringLength;
            String lastLetter=ans.substring(startSub,endSub);
            boolean letterAdded=false;
            for(int i=0;i<sizeQueue;i++)
            {
                CharOccurence letter=queue.poll();
                if(!lastLetter.contains(String.valueOf(letter.letter)))
                {
                    letter.occurence--;
                    ans.append(String.valueOf(letter.letter));
                    if(letter.occurence>0)
                        tmpQueue.add(letter);
                    letterAdded=true;
                    break;
                }
                else
                {
                    tmpQueue.add(letter);
                }
            }
            if(!letterAdded)
                return "";
            queue.addAll(tmpQueue);
        }
        return ans.toString();

    }
    class CharOccurence{
        public Character letter;
        public int occurence;
        public CharOccurence(Character letter, int occurence)
        {
            this.letter=letter;
            this.occurence=occurence;
        }
    }
}
class Solution {
public:
    string reorganizeString(string s) {
        
        // Step1: insert elements to the map so that we will get the frequency
        unordered_map<char, int> mp;
        for(auto i: s){
            mp[i]++;
        }
        
        //Step2: Create a max heap to store all the elements according to there frequency
        priority_queue<pair<int, char>> pq;
        
         for(auto it: mp){
            pq.push({it.second, it.first});
        }
        
        //Step3: Now take two elements from the heap and do this till the map becomes size 1
        // why one : cause we are taking two top elements like pq.top is a then will pop and again pq.top is b and will add to answer
        string ans = "";
        while(mp.size() > 1){
            //get the top two elements from heap
            char ch1 = pq.top().second;
            ans+=ch1;
            pq.pop();
            char ch2 = pq.top().second;
            ans+=ch2;
            pq.pop();
            
            //now reduce the size in the mp
            // now we have added two char in the ans so reduce the cound in map
            mp[ch1]--;
            mp[ch2]--;
            
            //Now check if it's size is still greater than 0 then push
            // if size is greater in map than 0 then we again need to push into the map so that we can make the ans string
            if(mp[ch1] > 0){
                pq.push({mp[ch1],ch1});
            }
            else{
                //if the size is 0 then decrese the map means erase the map
                mp.erase(ch1);
            }
            if(mp[ch2] > 0){
                pq.push({mp[ch2],ch2});
            }
            else{
                mp.erase(ch2);
            }
        }
        
        //Step4 : Now check wheather any element is present into it
        // Now we have zero size of the map so check top element size is greater than 1 or not if greater the we cannot split it since it''s only that char if not add to ans
        if(mp.size() == 1){
            if(mp[pq.top().second] > 1){
                return "";
            }
            ans += pq.top().second;
        }
        //returrn ans
        return ans;
    }
};
var reorganizeString = function(s) {
    const charMap = {};
    const res = [];

    // Store the count of each char
    for (let char of s) {
        charMap[char] = (charMap[char] || 0) + 1;
    }

    // Sort in descending order by count
    const sortedMap = Object.entries(charMap).sort((a, b) => b[1] - a[1]);

    // Check if we can distribute the first char by every other position.
    // We only need to check the first char b/c the chars are ordered by count
    // so if the first char succeeds, all following chars will succeed
    if (sortedMap[0][1] > Math.floor((s.length + 1) / 2)) return '';

    let position = 0;
    for (let entry of sortedMap) {
        const char = entry[0]
        const count = entry[1];
        for (let j = 0; j < count; j++) {
            // Distribute the current char every other position. The same char
            // will never be placed next to each other even on the 2nd loop
            // for placing chars in odd positions
            res[position] = char;
            position +=2;

            // This will only happen once since total number of chars
            // will be exactly equal to the length of s
            if (position >= s.length) position = 1;
        }
    }

    return res.join('');
};
Reorganize String