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

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

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

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

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

Repovive

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

Repovive.

Greedy Algorithms8 sections · 317 units14h total

Open in Course

Reorganize String - Implementation

The code

function reorganizeString(s)
 count := frequency map of s
 heap := max-heap of (count, char)
 for each (char, cnt) in count
 if cnt > (length of s + 1) / 2 then
 return ""
 heap.push((cnt, char))
 result := ""
 while heap.size() >= 2
 (cnt1, c1) := heap.pop()
 (cnt2, c2) := heap.pop()
 result := result + c1 + c2
 if cnt1 > 1 then heap.push((cnt1 - 1, c1))
 if cnt2 > 1 then heap.push((cnt2 - 1, c2))
 if heap.size() = 1 then
 result := result + heap.pop().char
 return result

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