Problem description:

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

1
2
Input: S = "aab"
Output: "aba"

Example 2:

1
2
Input: S = "aaab"
Output: ""

Note:

S will consist of lowercase letters and have length in range [1, 500].

Solution:

When we first see this problem, we should use an example to walk through it, and we can see that we need to know what character has the greatest occurrence in the string.

  1. Use an unordered_map to count occurrence
  2. Use priority queue to store the occurrence, it will automatically sort it.
  3. Put the character into the result string, take 2 different character at a time, this can ensure the outcome will not have same adjacent character.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string reorganizeString(string S) {
        /*
        1. count the frequency of each char
        2. put into priority queue
        3. the top 2 elements in queue must be the most frequently element, put them into result string first
        */
        unordered_map<char, int> map;
        for(auto c: S)
            map[c]++;
        
        priority_queue<pair<int, char>> q;
        for(auto n: map){
            if(n.second> (S.length()+1)/2) return ""; //Pigeonhole principal 
            q.push({n.second, n.first});
        }
        
        string res;
        while(q.size()>= 2){
            auto tmp1= q.top(); q.pop();
            auto tmp2= q.top(); q.pop();
            res.push_back(tmp1.second);
            res.push_back(tmp2.second);
            if(--tmp1.first > 0) q.push(tmp1);
            if(--tmp2.first > 0) q.push(tmp2);
        }
        if(!q.empty())
            res.push_back(q.top().second);
        return res;
    }
};

The goal is to first exhaust the most-frequent chars. We build a frequency dict of the letters in the string. We push all the letters into a max heap together with their -ve frequencies (max heap: high-freq letters are towards the top of the heap)
We pop two letters at a time from the heap, add them to our result string, decrement their frequencies and push them back into heap. Why do we have to pop two items/letters at a time you’re wondering? Because if we only pop one at a time, we will keep popping and pushing the same letter over and over again if that letter has a freq greater than 1. Hence by popping two at time, adding them to result, decrementing their freq and finally pushing them back into heap, we guranatee that we are always alternating between letters.

For example: for the string s = aab
The freq dict will be: d = {"a": 2, "b":1}
And the heap: h = [(-2, "a"), (-1, "b")]

After the first iteration:
h = [(-1, "a")]
and so on…
Edge Case:

NOTE [1]

  • Since we are always popping two items at a time, we will definitely run into an out of bounds error if we have an odd number of unique items in the given string. To avoid this, we need to make sure our heap at least has two items at any given time. We achive this by running our main logic inside a while len(heap) > 1 instead of a while heap

NOTE [2]

  • Again if the there is an odd number of unique letters in the string, there will be one last item/letter remaining in the heap when our loop terminates. Hence we need to examine that last item:
  • If the last item has a freq greater than 1: -> then return “” becasue we can’t escape having the same letter repeated contigiously.
  • else if the item has freq = 1, we pop it, add it to our result and we’re done.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def reorganizeString(self, S: str) -> str:
        d = {}
        for c in S:
            if c in d:
                # we want max heap
                d[c] -= 1
            else:
                d[c] = -1
        
        # Use Max heap to store
        hq = []
        for k, v in d.items():
            heapq.heappush(hq, (v, k))
        
        res = ""
        # we want to make the string separate by two characters, so pop out two each turn
        while len(hq) > 1:
            f1, c1 = heapq.heappop(hq)
            f2, c2 = heapq.heappop(hq)
            res+= str(c1+c2)
            if f1+1 != 0:
                heapq.heappush(hq, (f1+1, c1))
            if f2+1 != 0:
                heapq.heappush(hq, (f2+1, c2))
        if len(hq):
            # still 1 (freq, character) pair left
            f1, c1 = heapq.heappop(hq)
            
            if f1 < -1:
                return ""
            else:
                res += str(c1)
        return res

Solution - Sorting

  1. count letter appearance
  2. find the letter with most frequent.
  3. If the most frequent letter is over half of string, then return ""
  4. put the letter into even index number (0, 2, 4 …) char array
  5. put the letter into odd index number (1, 3, 5 …) char array
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reorganizeString(self, S: str) -> str:
        counter = collections.Counter(S)
        i, res, n = 0, [None] * len(S), len(S)
        for k in sorted(counter, key = counter.get, reverse = True):
            if counter[k] > n // 2 + (n % 2): return ""
            for j in range(counter[k]):
                if i >= n: i = 1
                print(i, k)
                res[i] = k; i += 2
        return "".join(res)

reference: