Rearrange characters in a string so that no character repeats twice. Input: abcccddaaabc output: cacacbadcdab

rearrange_strings_without_repeat.py

'''
Rearrange characters in a string so that no character repeats twice.

  Input: abcccddaaabc
  output: cacacbadcdab


First attempt:

Easist way. read the input and put it in a hashtable with counter
Read over hash table in a loop and find places to place char.
This way had flaw since it is not guarantee that what's left was the longest one. We need to use up longer strings first.

51:50: to write up code.
First attempt was over time and partially in correct.

Need to use Heap to keep the longest char and fill it with second longest char.
'''
class MaxHeap:
  def __init__(self):
    self.list = [None]
  
  def extract(self):
    if len(self.list) <= 1:
      return None

    value = self.list[1]
    self.swap(1, len(self.list) -1 )
    self.list.pop()
    self.bubbleDown(1)
    return value
  
  def get_length(self):
    return len(self.list) - 1
  
  def add(self, value):
    self.list.append(value)
    self.bubbleUp(len(self.list) - 1)

  def left(self, p):
    return 2 * p

  def right(self, p):
    return 2 * p + 1

  def parent(self, c):
    return c//2

  def swap(self, l, r):
    tmp = self.list[l]
    self.list[l] = self.list[r]
    self.list[r] = tmp

  def is_child(self, p, c):
    return self.list[p][1] > self.list[c][1]

  def bubbleDown(self, parent):
    if parent >= len(self.list) - 1:
      return
    
    left = self.left(parent)
    if left > len(self.list) -1:
      return
    right = self.right(parent)

    to_swap = left if right > len(self.list) -1 or self.is_child(left, right) == True else right

    if self.is_child(parent, to_swap) != True:
      self.swap(parent, to_swap)
      self.bubbleDown(to_swap)
  
  def bubbleUp(self, child):
    if child <= 1:
      return

    parent = self.parent(child)

    if self.is_child(parent, child)!= True:
      self.swap(parent, child)
      self.bubbleUp(parent)

def rearrage(input):
  dic = {}
  for c in input:
    dic[c] = 1 if c not in dic else dic[c] + 1
  
  heap = MaxHeap()

  for k in dic:
    heap.add([k, dic[k]])

  result = []

  last_char = None
  while heap.get_length() > 0:
    first = heap.extract()
    second = heap.extract()

    if second == None:
      if first[1] > 1 or first[0] == last_char:
        return []
      result.append(first[0])
      first[1] -= 1
    elif last_char == first[0]:
      result.append(second[0]) 
      second[1] -= 1
    else:
      result.append(first[0])
      first[1] -= 1

    last_char = result[-1]

    if first[1] > 0:
      heap.add(first)
    
    if second != None and second[1] > 0:
      heap.add(second)
  
  return "".join(result)


input = 'abcccddaaabc'
print("input = {}, output = {}".format(input, rearrage(input)))