Problem statement

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

Solution

Use counter to calculate frequency of each letter. If letter has frequency more than half of all elements, return empty string. Then let us sort letter by frequency and start to fill it: first using even indexes, then using odd indexes: for this I use d dictionary.

Complexity

Time complexity is O(n + A log A), where A is size of dictionary, space is O(n + A).

Code

class Solution:
    def reorganizeString(self, S):
        cnt, n = Counter(S), len(S)
        if max(cnt.values()) > (n + 1)//2: return ""
        Q = "".join(i*j for i,j in sorted(cnt.items(), key = lambda x: -x[1]))
        d = {i:j for i,j in zip(list(range(0,n,2)) + list(range(1,n,2)), range(n))}
        return "".join(Q[d[i]] for i in range(n))

Remark

Another way is to use priority heaps. Note, that this problem is special case of problem 0358 Rearrange String k Distance Apart, here k = 1