# Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are
#  not the same.
#
# If possible, output any possible result.  If not possible, return the empty string.
#
# Example 1:
#
# Input: S = "aab"
# Output: "aba"
#
# Example 2:
#
# Input: S = "aaab"
# Output: ""
#
# Note:
#
#     S will consist of lowercase letters and have length in range [1, 500].
import collections
import heapq


class Solution(object):
    # time complexity: O(N * logA), A: len(set(s)), N : len(S)
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        # time: O(N)
        count = collections.Counter(S)

        arr = [[-v, k] for k, v in count.iteritems()]

        res = []
        # knowledge usage of heapify
        # heap has the size of charactor number in S
        heapq.heapify(arr)

        while arr:
            # each time we pop two elements from heap
            # for test case vvvlo, we have {v:3, l:1, o:1}
            # so we will pop out v,l , then v,o, etc
            n, a = heapq.heappop(arr)
            n += 1
            res.append(a)
            # we try to pop in pair, but if this time, after pop one, then heap empty
            # just like {v:3, l:1, o:1} => {v:2,l:0,o:1} => {v:1,l:0,o:0}
            # if n < 0, means we still have element left, but we have no other to neighboaring them
            # then there is no possible result
            if not arr:
                if n < 0:
                    return ""
                break
            # pop pair, pop the first, then second
            m, b = heapq.heappop(arr)
            m += 1
            # time : O(N * logA), why? because res would finally has all chars as S has
            # in this while loop, each time we pop out one pair, we would call the heap operation 4 times
            # so it is O((N/2) * 4 * logA) => O(N * logA)
            res.append(b)

            if n < 0:
                heapq.heappush(arr, [n, a])
            if m < 0:
                heapq.heappush(arr, [m, b])

        return "".join(res)

    # references, so cool
    # time complexity : O( A * ( N + log(A)), N : len(S), A : len(set(S))
    def reorganizeString2(self, S):
        """
        :type S: str
        :rtype: str
        """
        N = len(S)
        tmp_list = []
        # time : O(A)
        for char in set(S):
            # tiime : O(A * N)
            counts = S.count(char)
            # if there is on char > half of S length, it is impossible to get solution
            # for ex, "VVVVVlo"
            if counts > (N + 1) / 2:
                return ""
            # for test case "VVVlo", we would get temp_list : ['vvv','l','o']
            tmp_list.append(counts * char)
        # after sort , [VVV,l,o] => [l,o,VVV]
        # time : A*log(A), A = len(set(S))
        tmp_list = sorted(tmp_list, key=len)
        # we got "lovvv"
        tmp_S = "".join(tmp_list)
        # time : O(N)
        ans = [0] * N
        # firstly pick the second half , for "lovvv", it is 'vvv'
        # we get ans = [v, , v, , v]
        ans[::2] = tmp_S[N / 2:]
        # then we got first half, which is 'lo', insert it
        # [v, l, v,o,v]
        ans[1::2] = tmp_S[:N / 2]
        return "".join(ans)


if __name__ == '__main__':
    print Solution().reorganizeString("aab")
    print Solution().reorganizeString("aabbbc")
    print Solution().reorganizeString("aabbbbc")
    print Solution().reorganizeString("vvvlo")

    print Solution().reorganizeString2("vvvlo")
    print Solution().reorganizeString2("aab")
    print Solution().reorganizeString2("aabbbc")
    print Solution().reorganizeString2("aabbbbc")
