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

reorganiseString.py

# Brute force. O(n!) I think, since it'll try all possible permutations
# TLE
class Solution:
    def reorganizeString(self, S: str) -> str:
        freqs = {}
        for c in S:
            if c not in freqs: freqs[c] = 1
            else: freqs[c]+= 1
        
        wc = []
        def backtrack():
            if len(wc) == len(S): return True
            
            for c in freqs: # for all remaining chars
                if freqs[c] > 0 and (len(wc) == 0 or c != wc[-1]): # if we can legally add this char
                    wc.append(c) # append it
                    freqs[c] -= 1 # remove it from freqs
                    if backtrack(): return True # recurse
                    freqs[c]+=1 # put it back
                    wc.pop() # pop backtrack
            
            return False # we tried everything and it found no solution
                    
        return ''.join(wc) if backtrack() else ''

# Greedy. O(n * log(numberOfDistinctCharacters))
# Accepted
import heapq
class Solution:
    def reorganizeString(self, S: str) -> str:
        
        heap = [(-S.count(c), c) for c in set(S)]
        heapq.heapify(heap)
        
        result = []
        while len(heap) >=2:
            maxCount, maxCountChar = heapq.heappop(heap)
            nMaxCount, nMaxCountChar = heapq.heappop(heap)
            if not len(result) or result[-1] != maxCountChar:
                result.append(maxCountChar)
                result.append(nMaxCountChar)
            else:
                result.append(nMaxCountChar)
                result.append(maxCountChar)
            if maxCount+1:  heapq.heappush(heap, (maxCount+1, maxCountChar))
            if nMaxCount+1: heapq.heappush(heap, (nMaxCount+1, nMaxCountChar))
            
        if not len(heap):
            return ''.join(result)
        else:
            lastCharCount, lastChar = heapq.heappop(heap)
            if not len(result) and lastCharCount < -1: return ''
            return ''.join(result+[lastChar]) if lastChar != result[-1] and lastCharCount == -1 else ''