Leetcode 1054. Distant Barcodes

Problem statement

https://leetcode.com/problems/distant-barcodes/

Solution

It is almost the same as Leetcode 0767 Reorganize String, heer we do not need to check if answer exists.

Complexity

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

Code

class Solution:
    def rearrangeBarcodes(self, S):
        cnt, n, Q = Counter(S), len(S), []
        for i, j in sorted(cnt.items(), key = lambda x: -x[1]):
            Q += [i] * j
        d = {i:j for i,j in zip(list(range(n, 2)) + list(range(1, n, 2)), range(n))}
        return [Q[d[i]] for i in range(n)]