Reorganize String

2 min read
LC-Medium

Oct 21, 2022

3 years ago

LeetCode

Solution

My first solution was creating a hashmap of character counts and sort of going back and forth between character of highest frequency and lowest frequency
- There is a weird edge case that prevented this solution from working- basically, it'll repeat a character when it cannot. This happened due to the fixed alternating nature of left and right, at a certain point, after picking a right character, you would again need to pick the next right character, but that couldn't happen in this solution
Instead the correct solution here uses a priority queue, and at each iteration, we choose the character with the highest frequency that's not equal to the last added character, and add that to the answer.
If the current popped character is the same as the character last added to our answer, we keep this aside and pop the second character from the heap
After adding the second popped character to our answer, we add back our first character to the heap and repeat
If we're trying to add a second character, we need to pop from the heap. If at this point if the heap is empty, we can return an empty string because we have only one leftover character and that cannot be added since it would violate the condition of there being no same characters existing one after the other
We can add an early exit condition that checks if the character with the highest frequency is greater than half the length of the string. If yes, we can immediately return an empty string since a valid answer is not possible.

Time	Space	Explanation
`O()`	`O()`

def reorganizeString(self, s: str) -> str: q = [(-freq, char) for char, freq in Counter(s).items()] heapify(q) new_s = [] while q: freq, char = heappop(q) if not new_s or new_s[-1] != char: new_s.append(char) if freq + 1: heappush(q, (freq + 1, char)) else: if not q: return '' next_freq, next_char = heappop(q) new_s.append(next_char) if next_freq + 1: heappush(q, (next_freq + 1, next_char)) heappush(q, (freq, char)) return ''.join(new_s)