767.md

740. Delete and Earn

Solution 1 (time O(n), space O(1))

class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        if len(S) < 2:
            return S
        n = len(S)
        cnt = collections.Counter(S)
        if max(cnt.values()) > (n + 1) / 2:
            return ""
        ans = ""
        queue = [(-x[1], x[0]) for x in cnt.items()]
        heapq.heapify(queue)
        while len(queue) > 1:
            _, c1 = heapq.heappop(queue)
            _, c2 = heapq.heappop(queue)
            ans += c1
            ans += c2
            cnt[c1] -= 1
            cnt[c2] -= 1
            if cnt[c1] > 0:
                heapq.heappush(queue, (-cnt[c1], c1))
            if cnt[c2] > 0:
                heapq.heappush(queue, (-cnt[c2], c2))
        if len(queue) > 0:
            ans += queue[0][1]
        return ans