Reorganize String [LC#767]

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. Return any possible rearrangement of s or return “” if not possible.

Intuition

Code

def reorganize_string(self, s: str) -> str:
    character_counts = Counter(s)
    n = len(s)
    if max(character_counts.values()) > (n + 1) // 2:
        return ""

    def interleaved_index_generator(n):
        for i in range(0, n, 2):
            yield i
        for i in range(1, n, 2):
            yield i

    characters = list(s)
    characters.sort(
        key=lambda char: (character_counts[char], char), 
        # break tie when 2 chars have same counts
        reverse=True
    )
    output = characters.copy()
    interleaved_index = interleaved_index_generator(n)
    for character in characters:
        output[next(interleaved_index)] = character
    return "".join(output)

Time complexity