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].
The description was taken from https://leetcode.com/problems/reorganize-string/.
#O(N(Log N)) Time, O(N) Spaceclass Solution: def reorganizeString(self, S: str) -> str: heap, output, seen = [], [], {} for char in S: if char not in seen: seen[char] = -1 else: seen[char] -= 1 for char in seen: heapq.heappush(heap, (seen[char], char)) while len(heap) > 1: most_frequent, char_one = heapq.heappop(heap) less_frequent, char_two = heapq.heappop(heap) output.append(char_one) output.append(char_two) if most_frequent + 1 < 0: heapq.heappush(heap, (most_frequent + 1, char_one)) if less_frequent + 1 < 0: heapq.heappush(heap, (less_frequent + 1, char_two)) if heap: frequency, char = heapq.heappop(heap) if frequency == -1: output.append(char) else: return "" return "".join(output)This problem is very similar to Task Scheduler and Sort Characters By Frequency.
The problem description isn't too clear about this, but there are only going to be two unique characters in the string. With that being said, the character we are going to have to worry about will be the most frequent, as that will be the one that may become adjacent to itself and wreck the string.
With the given constraints, we are going to want to have a somewhat greedy approach. Greedy approaches typically are to sort the given requirements and then continuously try to fit in either the cheapest or most expensive task at a time so that we can conserve the most resources.
In this case, the resources we are going to want to conserve are non-adjacent characters.
What we can do is use a hashmap to count the frequency of each character, throw the frequency along with the character into a max heap, and from there, continuously pop and push each character/frequency until we have run out of our resources. If there are even many characters, the heap will be empty by the end of this. If there are uneven many characters, then the last character must have a frequency of one or it will overlap with itself.
Let's start by initializing our heap, output array, and seen hashmap.
heap, output, seen = [], [], {}
It is important here not to use an empty string because strings are immutable, meaning if we want to add to a string we will have to copy it, then append to it each time since we can't change the elements. This would require a quadratic time complexity.
Next, we will go through each character in the string and count its frequency using our hashmap.
for char in S:
If the character isn't in the hashmap already, we will put it there with an initial count of negative one.
if char not in seen: seen[char] = -1
If it is in the hashmap, we will decrement the count by one.
else: seen[char] -= 1
To create a makeshift max heap from a min heap, we are making the heap input, the frequency, negative so that the largest frequency in the heap becomes the smallest when negative.
After we have counted frequencies, we will go through each character in the hashmap and push its frequency and itself into the heap. It is important the frequency is first because the heap sorts on the first value inside the tuple.
for char in seen: heapq.heappush(heap, (seen[char], char))
Next, we will make a loop that will run until the heap size is greater than one.
The size has to be greater than one because if it wasn't and we tried to pop two items off, we'd get an index out of bounds error.
while len(heap) > 1:
Within each iteration, we will pop the most and second-most frequent characters off of the heap then append them out of the output. Popping two numbers at a time ensures that the most frequent element won't keep getting placed back next to itself.
most_frequent, char_one = heapq.heappop(heap) less_frequent, char_two = heapq.heappop(heap) output.append(char_one) output.append(char_two)
Then, if the frequency of each character plus one is less than zero, then we still have an inventory of the character and will need to keep appending it to the output within a later iteration.
if most_frequent + 1 < 0: heapq.heappush(heap, (most_frequent + 1, char_one)) if less_frequent + 1 < 0: heapq.heappush(heap, (less_frequent + 1, char_two))
Otherwise, we are out of stock and can't push it back onto the heap.
Once our heap has less than two characters in it, we will need to check if there is still one of the characters in it.
If there is, then the frequency needs to be negative one, meaning we only have one more of the character inside our inventory. If it is less than negative one, then that means it is going to become adjacent to itself. In this case, we will return an empty string as the problem description states.
Otherwise, we will append the character to the output.
if heap: frequency, char = heapq.heappop(heap) if frequency == -1: output.append(char) else: return ""
If we've gotten this far, we have either taken care of one last character that we needed to append to the string, or we had an even amount of character frequencies.
In any case, we will join the output array into a string and return it.
return "".join(output)