Class Solution

Python/reorganize-string.py:9–24

space complexity: O(N)
'''
class Solution:
    def reorganizeString(self, S: str) -> str:
        n = len(S)
        a= []
        
        for c,x in sorted((S.count(x), x) for x in set(S)):
            if c > (n+1)/2: # not possible
                return ''
            a.extend(c*x)
        
        # empty list
        ans = [None] * n
        
        # placing letters to make possible result
        ans[::2], ans[1::2] = a[n//2:], a[:n//2]
        return "".join(ans)