767. Reorganize String

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:

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].

Solution

MaxHeap, time O(n * log k), space O(k), k is the count of distinct numbers

起初的想法是将字符按照freq升序排列，然后遍历，将新的字符插到现有的reorganize str中去。但这样有一个问题，考虑这个test case："abbbccccc"，用这种解法会返回""，但实际上应该返回"cacbcbcbc"。所以不能批量append，而是该一个字符一个字符append，append完一个字符，将它重新放入queue中以待后续处理。

class Solution {
    public String reorganizeString(String S) {
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < S.length(); ++i) {
            freq.put(S.charAt(i), freq.getOrDefault(S.charAt(i), 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Character, Integer>> queue
            = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        queue.addAll(freq.entrySet());
        StringBuilder sb = new StringBuilder();
    
        while (!queue.isEmpty()) {
            Map.Entry<Character, Integer> first = queue.poll();
            char c = first.getKey();
            int count = first.getValue();
            
            if (sb.length() == 0 || sb.charAt(sb.length() - 1) != c) {
                sb.append(c);
            } else if (!queue.isEmpty()) {  // find another char to set in between
                Map.Entry<Character, Integer> second = queue.poll();
                sb.append(second.getKey()).append(c);
                if (second.getValue() > 1) {
                    second.setValue(second.getValue() - 1);     // push second back
                    queue.offer(second);
                }
            } else {
                return "";
            }
            
            if (count > 1) {    // push back
                first.setValue(--count);
                queue.offer(first);
            }
        }
        
        return sb.toString();
    }
}