Leetcode 767. Reorganize String

Problem

Leetcode 767 - Reorganize String

Example:

Input: s = "aab"
Output: "aba"

Input: s = "aaab"
Output: ""

Approach

First we want to get freq where it consists of every character and frequency in the dictionary.

Once we do, we get an array of its keys and value as pair. We can heapify this since we want maximum frequency character first.

We can have a prev = None at first then alternate to keep track of previous pair

• if prev exists and alph is empty, we return false
• heappop from alph
• add char to res
• if prev exists heappush(alph, prev), then set prev to None again
• if count != 0, we set prev = [cnt, char]

Here is the Python code for the solution:

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = {}
        for ch in s:
            if ch not in freq:
                freq[ch] = 0
            freq[ch] -= 1

        alph = []
        for key, val in freq:
            alph.append([key, val])
        
        heapq.heapify(alph)
        res = ''
        prev = None

        while alph or prev:
            if prev and not alph:
                return ''
            
            cnt, char = heapq.heappop(alph)
            res += char
            cnt += 1

            if prev:
                heapq.heappush(alph, prev)
                prev = None
            if cnt != 0:
                prev = [cnt, char]
        
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$