767. Reorganize String

Problem Statement

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.

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

• 1 <= s.length <= 500

• s consists of lowercase English letters.

Intuition

Approach:
Maintain count of all the things and then start placing the things alternatively 
on the basis of frequency 

Three conditions- 1) highest frequency element > len/2 -> not possible
As it cannot take alternating position
______
a a a   if a is 4 times then not possible

Else once completed , start from index 1 and fill till end

Links

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

Video Links

Approach 1:

C++

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char,int> mp;
        priority_queue<pair<int, char>> pq;
        for(auto &it: s)
            mp[it]++;

        for(auto &it: mp){
            char alp = it.first;
            int count = it.second;

            pq.push({count, alp});
        }

        string temp(s.size(),'X');
        int count=pq.top().first;

        if(count > (s.size()+1)/2)
            return "";

        int index = 0;
        char alp = pq.top().second;

        while(count--){
            temp[index] = alp;
            index+=2;
        }

        if(pq.top().first == (s.size()+1)/2)
            index = 1;

        pq.pop();

        while(!pq.empty()){
            int count = pq.top().first;
            char alp = pq.top().second;

            while(count--){
                if(index >= temp.size())
                    index = 1;
                temp[index] = alp;
                index+=2;
            }
            pq.pop();
        }

        return temp;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems