#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/greedy-optimization/reorganize-string-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/greedy-optimization/reorganize-string-implementation

Repovive

Reorganize String - Implementation - Greedy Optimization | Greedy Algorithms | Repovive

Repovive.

Greedy Algorithms8 sections · 317 units14h total

Open in Course

Reorganize String - Implementation

The code

Here is the solution:

function reorganizeString(s)
 count := frequency map of characters
 maxFreq := maximum frequency
 if maxFreq > (length + 1) / 2 then
 return ""
 heap := max-heap of (freq, char)
 for each (char, freq) in count
 heap.push((freq, char))
 result := []
 prev := null
 while heap is not empty
 (freq, char) := heap.pop()
 result.append(char)
 if prev is not null then
 heap.push(prev)
 if freq > 1 then
 prev := (freq - 1, char)
 else
 prev := null
 return join(result)

Time: $O(n \log k)$ where $k$ is alphabet size. Space: $O(k)$ .