Reorganize String

Question

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

Input: s = "aaab"
Output: ""

Refraiming the problem

1. 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.
2. Lets try a few combinations
Copy

string = "aaaa"

"X" = any other character 

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

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

"X" = 3 possible
ReorganizedString = "aXaXaXa"

3. We need atleast 3 other characters for 4 a's(character of highest frequency) to provide buffer around elements that are similar.
1. 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.
4. Imagine all other characters (X) were the same, let's say "b". This is the maximum possible similarity between the characters in betweem
1. Insight 2: b had a higher frequency than a--The higher frequency envelops the lower frequencies.
Copy

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"

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

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

1. 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.

2. What kind of heap will give us the elements with the highest frequency on top? A max heap.
3. How will the structure look like, this will be similar to heap with a pay load.
1. The first element (i.e. 3, 2) represents the priority, and the second element represents the type of character.

4. 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.


5. 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.
Copy

a = 4
b = 3

"ab" instead of "aa"

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

a = 2
b = 1

firstiteration = "ab"

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

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

#Instead of 
while heap:
	#poping


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

8. 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.
Copy

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

9. 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

1. Create a frequency counter.
Copy

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

2. 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.
Copy

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

        heapify(heap)

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

#O(N) time
heapify(heap)

1. can also be done like this but is more costly
Copy

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

4. 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.
Copy

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])

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.

5. 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.
Copy

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

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

    else:
        reorganizedString += char

6. Return the reorganized String
Copy

return reorganizedString

7. 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.
1. While adding
Copy

#instead of
reorganizedString = ""
reorganizedString += char1

reorganizedString = []
reorganizedString.append(char1)

2. returning
Copy

return "".join(reorganizedString)

Code

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)

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