767.Reorganize_String(Medium).md

767. Reorganize String (Medium)

Date and Time: Feb 16, 2025, 19:17 (EST)

Link: https://leetcode.com/problems/reorganize-string

Question:

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

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

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

• 1 <= s.length <= 500

• s consists of lowercase English letters.

Walk-through:

1. Build hashmap for each char with their counts.

2. Convert hashmap into maxHeap with [-counts, char].

3. First pop the most frequent char char1 from maxHeap[], then append it to ans[] if ans[] is empty or char1 != ans[-1] it doesn't equal to the last char in ans[] (avoid duplicate). If not, we are going pop the second most frequent char char2, but before we do that, we need to check if maxHeap[] now is empty, if so, we return "". Otherwise, we can append char2. Don't forget to update the counts + 1 after we append char1 or char2 correspondingly. If we add char2, don't forget to put back char1 with just count1.

maxHeap:

class Solution:
    def reorganizeString(self, s: str) -> str:
        # Count each letter with frequency
        # Use minHeap to place the most frequent letter first, then put the second most frequent letter
        # Before we pop the 2nd letter, check if not minHeap, if so, and cnt for 1st char > 0, return ""

        # TC: O(nlogk), n=len(s), k=#distinct chars in s, SC: O(k)
        hashmap = {}
        maxHeap = []
        ans = ""
        for i in s:
            hashmap[i] = hashmap.get(i, 0) + 1
        # Convert hashmap to maxHeap, O(klogk)
        for key, cnts in hashmap.items():
            heapq.heappush(maxHeap, [-cnts, key])
        # Fill in ans
        while maxHeap:
            cnt1, c1 = heapq.heappop(maxHeap)
            ans += c1
            if len(maxHeap) > 0:
                cnt2, c2 = heapq.heappop(maxHeap)
                ans += c2
                # Push back c2 if cnt2 > 1
                if cnt2 < -1:
                    heapq.heappush(maxHeap, [cnt2+1, c2])
            # When we have no c2 and cnt1 is more than 1, return ""
            elif not maxHeap and cnt1 < -1:
                   return "" 
            # Push back c1
            if cnt1 < -1:
                heapq.heappush(maxHeap, [cnt1+1, c1])
        return ans

Time Complexity: $O(nlog\ k)$
Space Complexity: $O(k)$