LC767 Reorganize String

"""
main idea: count the char in the string, check if max_cnt char has reached (len(S)+1)//2, if yes return ""; otherwise, insert in odd position and even position seperately 

"""
class Solution:
    def reorganizeString(self, S: str) -> str:
        # time O(N+AlgA)=> O(N) space O(A) 
        if not S:
            return ""
        d = {}
        for ch in S:
            if ch not in d:
                d[ch] = 1
            else:
                d[ch] += 1
        # sort dictionary items by cnt, makes future iteration easier
        # can be optimized by bucket sort.  
        tps = sorted(d.items(),key = lambda k: k[1],reverse = True)
        if tps[0][1] > (len(S)+1)//2:
            return ""
        res = ['']*len(S)
        idx = 0
        # odd insertion
        for i in range(0,len(S),2):
            # max char has used out 
            if d[tps[idx][0]] < 1:
                idx += 1
            d[tps[idx][0]] -= 1
            res[i] = tps[idx][0]
        # even insertion
        for i in range(1,len(S),2):
            if d[tps[idx][0]] < 1:
                idx += 1
            d[tps[idx][0]] -= 1
            res[i] = tps[idx][0]
        return ''.join(res)