🧵

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: ""

Leetcode

Refraiming the problem

Is there a way to organize the string "aaaa" so that no two adjacent characters are the same? Unfortunately, this is not possible without introducing additional characters to be inserted between the "a"s.
Lets try a few combinations

string = "aaaa"

"X" = any other character 

"X" = 1 not possible
ReorganizedString = "aXaaa"

"X" = 2 not possible
ReorganizedString = "aXaXaa"

"X" = 3 possible
ReorganizedString = "aXaXaXa"

We need atleast 3 other characters for 4 a's(character of highest frequency) to provide buffer around elements that are similar.

Insight 1: The difference between the frequency of the most frequent character (in this case, 'a') and the frequencies of all other characters (in this case, 'X') must be 1.

Imagine all other characters (X) were the same, let's say "b". This is the maximum possible similarity between the characters in betweem

Insight 2: b had a higher frequency than a--The higher frequency envelops the lower frequencies.

LegitReorganizedString = "aXaXaXa" = "abababa" 

Lets increase X = 5 while all "X" are b's

"X" = 5 not possible with the previous arrangemnet where we 
started with a in the begining.
ReorganizedString = "aXaXaXaXX" or "ababababb"

the new order that will be possible will be 
"XaXaXaXaX"

From insight 2, we discover that we only need to consider the most frequent character; the others will take care of themselves.

a = 4
b = 3
LegitReorganizedString = "abababa"

'b's take care of themselves as 'a' has a higher frequency and will wrap around them. If there are many characters with multiple frequencies. The higher frequency will always wrap arond the lower frequenies. This order will continue to frequencies below.

Intuition

The goal is to prioritize most frequent characters. These characters will be added to the string first.

We need a structure that keeps track of the only most frequent character.

And once the character is taken out sorts the whole structure A heap is a structure that can keep track of the elements while keeping the top frequency element, and be updated without needing to resort the whole structure.

What kind of heap will give us the elements with the highest frequency on top? A max heap.
How will the structure look like, this will be similar to heap with a pay load.

The first element (i.e. 3, 2) represents the priority, and the second element represents the type of character.

From the heap, we remove the two types of characters with the highest priority. We then add them to our resulting string, decrement their frequencies, and push them back into the heap if either still has remaining frequency.

Why two items at a time? Popping two different characters together (and adding them to the string while reducing their frequency) ensures that we don't add the same letter twice. This way, we always alternate between different letters.

a = 4
b = 3

"ab" instead of "aa"

What if in the end there is only one type of character left. What will we do?

a = 2
b = 1

firstiteration = "ab"

a = 1
secondIteration "aba" # we are trying to pop two characters from the heap

We will make sure that we only keep poping two items if there are two items to pop form.

#Instead of 
while heap:
	#poping


#we will do 
while len(heap) > 1:
	#poping

After creating the string and having only one type of element left in the heap, we need to determine if the remaining character can form a valid string. This is only possible if the frequency is 1. If the frequency of the remaining item is greater than 1, we must return an empty string because it indicates that a string cannot be formed.

heap = [2:a]
not possible = "aa"

We are given a string as input, and we need to determine the frequency of each item. To do so, we will iterate over the string and create a frequency counter for each type of character.

Let's write the algorithm

Create a frequency counter.

count = {}
for char in s:
    if char in count:
        count[char]+=1
    else:
        count[char] = 1

Create a payload structure using the values from the counter. For each character, the first item in the payload should be the count of the character, and the second item should be the character itself.

        
heap = []
for char,freq in count.items():
    heap.append([-freq,char])

        heapify(heap)

Heapify the list, the first item will be used to determine the sortedness of the array.

#O(N) time
heapify(heap)

can also be done like this but is more costly

#Time O(NlogN)
heap = []
for char,freq in count.items():
    heappush(heap,[-freq,char])

While we have more than one item in the heap, we pop out the two most frequent items, add them to the reorganized string, and add the same type of characters back into the heap with one less count, if their frequency is more than one.

To create a max heap in Python, we can simulate it by adding a negative sign when adding elements to the heap. The information from the heap can be used by "positivifying" the elements (as done under the comment "positivify") and while pushing them back.

If the frequency of the remaining item is greater than 1, we return an empty string. If not, we add the remaining character to the reorganized string.

# still heap remaining with one character
if heap:
    freq,char = heappop(heap)

    #positivify 
    freq = -1 * freq
    
    if freq > 1:
        return ""

    else:
        reorganizedString += char

Return the reorganized String

return reorganizedString

Optimization : strings are immutable in python so adding to a string is actually an O(len(string)) operation. We can simply add to an array and then use the "".join(list), to return the list as a string.

While adding


#instead of
reorganizedString = ""
reorganizedString += char1

reorganizedString = []
reorganizedString.append(char1)

returning

return "".join(reorganizedString)

Code

Complexities

Time Complexity: O(Nlog(26)) = O(N)

Space Complexity: O(26)

Since there are at most 26 pairs in the heap, the upper bound for time complexity would be O(nlog(26)) which simplifies to O(n).

Sandbox (press on Edit code to try with your own inputs)

Dedications

💡

Really good solution

LegitReorganizedString = "aXaXaXa" = "abababa" Lets increase X = 5 while all "X" are b's "X" = 5 not possible with the previous arrangemnet where we started with a in the begining. ReorganizedString = "aXaXaXaXX" or "ababababb" the new order that will be possible will be "XaXaXaXaX"

reorganizedString = "" while len(heap) > 1: freq1,char1 = heappop(heap) freq2,char2 = heappop(heap) reorganizedString += char1 reorganizedString += char2 #positivify freq1 = -1 * freq1 freq2 = -1 * freq2 # substract freq1 -= 1 freq2 -= 1 #more to add? if freq1 > 0: heappush(heap,[-freq1,char1]) if freq2 > 0: heappush(heap,[-freq2,char2])

# still heap remaining with one character if heap: freq,char = heappop(heap) #positivify freq = -1 * freq if freq > 1: return "" else: reorganizedString += char

from heapq import heapify, heappop,heappush class Solution: def reorganizeString(self, s: str) -> str: count = {} for char in s: if char in count: count[char]+=1 else: count[char] = 1 heap = [] for char,freq in count.items(): heap.append([-freq,char]) heapify(heap) reorganizedString = [] while len(heap) > 1: freq1,char1 = heappop(heap) freq2,char2 = heappop(heap) reorganizedString.append(char1) reorganizedString.append(char2) #positivify freq1 = -1 * freq1 freq2 = -1 * freq2 # substract freq1 -= 1 freq2 -= 1 #more to add? if freq1 > 0: heappush(heap,[-freq1,char1]) if freq2 > 0: heappush(heap,[-freq2,char2]) # still heap remaining with one character if heap: freq,char = heappop(heap) #positivify freq = -1 * freq if freq > 1: return "" else: reorganizedString.append(char) return "".join(reorganizedString)