767. Reorganize String #

Problem #

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:

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

Example 2:

Input: S = "aaab"
Output: ""

Note:

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

Problem Summary #

Given a string, rearrange the string so that every two adjacent characters are different. If this can be achieved, output the resulting string; if adjacent characters cannot all be made different, output an empty string.

Solution Ideas #

There are 2 approaches to this problem. The first approach is to first count the occurrence frequency of each character, then sort by frequency from high to low. The specific method is the same as Problem 451. If the frequency of any letter exceeds (len(string)+1)/2, then return an empty string. Otherwise, output the final string that satisfies the problem requirements. After sorting by frequency, use 2 pointers: one starting from 0, and the other starting from the middle position, then take one character at a time and concatenate them.

The second approach is to use a priority queue. Each node is a struct with 2 fields: one field records which character it is, and the other field records the frequency of this character. Use higher frequency as higher priority, and build the priority queue with a max-heap. Note that in the successfully built priority queue, each repeated letter has only one node, with its frequency recorded in the frequency field of the struct. An additional auxiliary queue is also needed. Each time, dequeue the highest-priority element from the priority queue, then decrease its frequency by one, and append this character to the final result. Then enqueue this node. The purpose of enqueueing is to check whether the frequency of this node has decreased to 0; if it is still not 0, insert it back into the priority queue.

    string reorganizeString(string S) {
        vector<int> mp(26);
        int n = S.size();
        for (char c: S)
            ++mp[c-'a'];
        priority_queue<pair<int, char>> pq;
        for (int i = 0; i < 26; ++i) {
            if (mp[i] > (n+1)/2) return "";
            if (mp[i]) pq.push({mp[i], i+'a'});
        }
        queue<pair<int, char>> myq;
        string ans;
        while (!pq.empty() || myq.size() > 1) {
            if (myq.size() > 1) { // Note that this must be greater than 1; if it is equal to 1, the element with high frequency will keep being output, and the answer will be incorrect.
                auto cur = myq.front();
                myq.pop();
                if (cur.first != 0) pq.push(cur);
            }
            if (!pq.empty()) {
                auto cur = pq.top();
                pq.pop();
                ans += cur.second;
                cur.first--;
                myq.push(cur);
            }
        }
        return ans;
    }

Code #

package leetcode

import (
	"sort"
)

func reorganizeString(S string) string {
	fs := frequencySort767(S)
	if fs == "" {
		return ""
	}
	bs := []byte(fs)
	ans := ""
	j := (len(bs)-1)/2 + 1
	for i := 0; i <= (len(bs)-1)/2; i++ {
		ans += string(bs[i])
		if j < len(bs) {
			ans += string(bs[j])
		}
		j++
	}
	return ans
}

func frequencySort767(s string) string {
	if s == "" {
		return ""
	}
	sMap := map[byte]int{}
	cMap := map[int][]byte{}
	sb := []byte(s)
	for _, b := range sb {
		sMap[b]++
		if sMap[b] > (len(sb)+1)/2 {
			return ""
		}
	}
	for key, value := range sMap {
		cMap[value] = append(cMap[value], key)
	}

	var keys []int
	for k := range cMap {
		keys = append(keys, k)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(keys)))
	res := make([]byte, 0)
	for _, k := range keys {
		for i := 0; i < len(cMap[k]); i++ {
			for j := 0; j < k; j++ {
				res = append(res, cMap[k][i])
			}
		}
	}
	return string(res)
}