Reorganize String — LeetCode 767 Python Solution

The problem

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.

Example

Input

s = "aab"

Output

"aba"

Python solution

class Solution:
    def reorganizeString(self, s: str) -> str:
        n = len(s)
        cnt = Counter(s)
        mx = max(cnt.values())
        if mx > (n + 1) // 2:
            return ''
        i = 0
        ans = [None] * n
        for k, v in cnt.most_common():
            while v:
                ans[i] = k
                v -= 1
                i += 2
                if i >= n:
                    i = 1
        return ''.join(ans)

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 767. Reorganize String is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems