LeetCode 767. Reorganize String

December 09, 2020

Claims (that I'm not going to prove):

For an input of length $n$ , if there is any character, $c$ , such that $count(c) \gt ceil(\frac{n}{2})$ , any reorganized string must have at least two adjacent characters that are both $c$ .
Our algorithm will work if it adds characters one by one and the highest character count is always $\leq ceil(\frac{n_i}{2}) \forall 0 \leq n_i \leq n$ .

If at each step we add the highest count character, that condition will always hold. We can have repeats, though, so if the highest count character is a repeat, we can use the second highest on that step instead. At worst, the highest count will be reducing by $\frac{1}{2}$ each step and that will keep it under the limit from claim 2.

We build our count map and our heap in $O(n)$ time and space.

The loop to build our result string has $n$ iterations and takes $O(log(n))$ time per iteration due to the heap pops and pushes.

This algorithm is $O(nlog(n))$ .

from collections import defaultdict
import heapq
import math
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.reorganizeString("aab"), "aba")
        self.assertEqual(self.s.reorganizeString("aaab"), "")

    def test_simple(self):
        self.assertEqual(self.s.reorganizeString("z"), "z") 
        self.assertEqual(self.s.reorganizeString("aabbcc"), "abcabc") 
        self.assertEqual(self.s.reorganizeString("aaaabbbccd"), "ababacabcd")

    def test_outlier(self):
        self.assertEqual(self.s.reorganizeString("aaabc"), "abaca")
        self.assertEqual(self.s.reorganizeString("aaaabbccd"), "abacabacd")
        self.assertEqual(self.s.reorganizeString("aaabbcc"), "abacabc")

class MaxHeap:

    def __init__(self, i):
        self._h = [(-e[0], e[1]) for e in i]
        heapq.heapify(self._h)

    def __len__(self):
        return len(self._h)

    def push(self, e):
        heapq.heappush(self._h, (-e[0], e[1]))

    def pop(self):
        e = heapq.heappop(self._h)
        return (-e[0], e[1])

    def peek(self):
        e = self._h[0]
        return (-e[0], e[1])

class Solution:

    def reorganizeString(self, S: str) -> str:
        counts = defaultdict(int)
        maxc = 0
        for c in S:
            counts[c] += 1
            maxc = max(maxc, counts[c])
        if maxc > math.ceil(len(S)/2):
            return ""
        heap = MaxHeap([(c,s) for s,c in counts.items()])
        res = ""
        while heap:
            nxt = heap.pop()
            if res and res[-1] == nxt[1]:
                tmp = heap.pop()
                heap.push(nxt)
                nxt = tmp
            res += nxt[1]
            if nxt[0] > 1:
                heap.push((nxt[0]-1, nxt[1]))
        return res

if __name__ == "__main__":
    unittest.main()