Skip to main content

Reorganize String

Question​

None

Example 1
Input: "aab"
Output: "aba"

Solution​

all//Reorganize String.py


def reorganizeString(S):
    length = len(S)
    counts = collections.Counter(S)

    max_char = max(counts, key=counts.get)
    max_val = counts[max_char]

    if max_val > (length + 1) / 2:
        return ""

    char, freq = zip(*sorted(counts.items(), key=lambda x: x[1], reverse=True))

    res = [''] * length
    i = 0

    while freq:
        res[i] = char[0]
        freq = freq[1:]
        char = char[1:]
        i += 2

        if i >= length:
            i = 1

    return ''.join(res)