Reorganise String

Lecture 75 :- Reorganise String

Reorganizing a string means rearranging its characters in such a way that no two adjacent characters are the same. The problem of reorganizing a string is often referred to as the "Task Scheduler" problem.

Here's the algorithm to reorganize a string:

1. Calculate the frequency of each character in the string and store it in a frequency map.
2. Create a priority queue (max heap) to store characters based on their frequencies.
3. While the priority queue is not empty, do the following: a. Extract the character with the highest frequency (top of the priority queue) and append it to the result string. b. Decrease the frequency of the extracted character in the frequency map. c. If the frequency of the extracted character is greater than 0, add it back to the priority queue. d. If there are still characters left in the priority queue, repeat the process, trying to extract a different character than the one extracted previously.

If it's not possible to reorganize the string (i.e., when there are two or more characters with the same highest frequency, and their positions cannot be arranged such that no two adjacent characters are the same), then return an empty string.

Here's a Python function to implement the algorithm:

pythonCopy code

import heapq from collections import Counter def reorganize_string(s):    freq_map = Counter(s)    max_heap = [(-freq, char) for char, freq in freq_map.items()]    heapq.heapify(max_heap)    result = []    while len(max_heap) >= 2:        freq1, char1 = heapq.heappop(max_heap)        freq2, char2 = heapq.heappop(max_heap)        result.append(char1)        result.append(char2)        if freq1 + 1 < 0:            heapq.heappush(max_heap, (freq1 + 1, char1))        if freq2 + 1 < 0:            heapq.heappush(max_heap, (freq2 + 1, char2))    if max_heap:        freq, char = heapq.heappop(max_heap)        if freq < -1:            return ""        result.append(char)    return "".join(result) # Example usage: string = "aab" print(reorganize_string(string))  # Output: "aba"

Keep in mind that this algorithm assumes the input string only contains lowercase letters. The time complexity of this algorithm is O(N log N), where N is the length of the input string, due to the heap operations. The space complexity is O(N) as we use a frequency map and a max heap to store characters and their frequencies.