767. Reorganize String

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.

Note: lastPoppedCount > 1 and not 0

def reorganizeString(self, s: str):

       

    res = ""

    freqs = Counter(s)

    pQ = [(-count, ch) for ch, count in freqs.items()]

    heapq.heapify(pQ)                        

    lastPoppedCount = 0

    while pQ:

        negCount, ch = heapq.heappop(pQ)

        if lastPoppedCount > 1: # Tricky that it is not 0

            heapq.heappush( pQ, (-(lastPoppedCount-1), lastPoppedChar) )            

        res += ch

        lastPoppedCount, lastPoppedChar = -negCount, ch

                                   

    return res if len(res) == len(s) else ""

No Sort O(N):

1. count letter appearance and store in hash[i]
2. find the letter with largest occurence.
3. put the letter into even index numbe (0, 2, 4 ...) char array
4. put the rest into the array

    public String reorganizeString(String S) {
        int[] hash = new int[26];
        for (int i = 0; i < S.length(); i++) {
            hash[S.charAt(i) - 'a']++;
        } 
        int max = 0, letter = 0;
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] > max) {
                max = hash[i];
                letter = i;
            }
        }
        if (max > (S.length() + 1) / 2) {
            return ""; 
        }
        char[] res = new char[S.length()];
        int idx = 0;
        while (hash[letter] > 0) {
            res[idx] = (char) (letter + 'a');
            idx += 2;
            hash[letter]--;
        }
        for (int i = 0; i < hash.length; i++) {
            while (hash[i] > 0) {
                if (idx >= res.length) {
                    idx = 1;
                }
                res[idx] = (char) (i + 'a');
                idx += 2;
                hash[i]--;
            }
        }
        return String.valueOf(res);
    }